오답노트 - AC

한달 전에 풀고 포스팅했던 기억이 나서, 쉽게 풀릴줄 알았는데 꽤 애를 먹었다. 이번에는 Delete때 마다, 배열의 앞, 뒤로 원소를 빼는 것이 아니라, 포인터 두개를 활용해 문제를 풀었다.


오답노트 - 내리막길

오늘의 문제 겸 오답노트로 내리막길을 다시 풀어보았다. 얼핏 기억이 나서 dp를 사용한 DFS로 문제를 풀었는데 자꾸 시간초과가 발생했다. 그러다가 또 못참고 이전에 내가 썻던 설명을 봐버렸다. 내일 한번 더 풀어봐야겠다.

지나간 길의 목록들을 달고다니면서 DFS를 수행한것이 시간복잡도가 증가한 원인이었다. 아래의 코드는 시행착오를 겪었던 코드이다.

풀었다!

Crepe


CODE - 시간초과

import sys
read=sys.stdin.readline

m,n=map(int,read().split())
MAP=list(list(map(int,read().split())) for _ in range(m))

dp=list(list(-1 for _ in range(n)) for _ in range(m))
dp[-1][-1]=1

dx=[1,0,0,-1]
dy=[0,1,-1,0]

def dfs(save):
    a,b=save[-1][0],save[-1][1]
    for x,y in zip(dx,dy):
        ax,by=a+x,b+y
        if 0<=ax<m and 0<=by<n and MAP[ax][by]<MAP[a][b]:
            if dp[ax][by]==-1:
                dfs(save+[[ax,by]])
            else:
                for i,j in save:
                    if dp[i][j]==-1:
                        dp[i][j]+=(dp[ax][by]+1)
                    else: dp[i][j]+=dp[ax][by]

dfs([[0,0]])
print(dp[0][0])

ABCDE


BFS로 풀지 DFS로 풀지 헷갈렸던 문제다. BFS로도 풀 수는 있는 것 같았으나 결국 DFS로 해서 풀었다.

CODE

import sys
read=sys.stdin.readline

n,m=map(int,read().split())

friends=dict()
for _ in range(m):
    a,b=map(int,read().split())
    if a in friends:
        friends[a].append(b)
    else: friends[a]=[b]
    if b in friends:
        friends[b].append(a)
    else: friends[b]=[a]

check=list(0 for _ in range(n))

cnt=0
#cnt를 사용하지 않고, check배열의 1의 개수로
#문제의 조건을 판단하면 시간초과가 발생했다.

def dfs(x):
    global cnt
    check[x]=1
    cnt+=1
    if cnt==5:#깊이가 5 >> ABCDE를 만족하는 친구들이 존재한다는 뜻이다.
        print(1)
        sys.exit()

    for i in friends[x]:
        if check[i]==0:
            dfs(i)
    cnt-=1
    check[x]=0

for i in range(n):
    dfs(i)
#종료되지 않고 여기까지 넘어오면 ABCDE를 만족하는 친구들이 존재하지 않는다는 뜻이다.
print(0)




CODE

풀어야 할 문제

  • 스타트 택시
  • 미네랄
  • 회전 초밥
  • 아기 상어
  • 꼬인 전깃줄, 전깃줄 -2