leetcode bfs, dp에 대한 새로운 깨달음..

음 여태까지 코드를 이해하지 못하고 짰었는데 이번에 leetcode의 bfs를 공부하다가 조금 깨달음을 얻었다. 나혼자서 코드를 짤수 있을것같다는 깨달음이라 그래야하나. 지금까지 백준에서 '정형화된' bfs문제만을 풀다보니, bfs문제는 대충 나름의 그런 특징이 있었다. 예를 들면 'n x n 크기의 맵에서, 상하좌우로 뻗어나가는 설정' 이런게 있으면 bfs소스코드를 찾아서 이리저리 기워맞추면 문제가 어느정도 풀렸고, 실제로 이런 문제가 많았다.(아니면 다른 문제도 있는데 내가 실력이 낮아서 몰랐거나, 못 깨달았거나이다.)

bfs코드를 짤 때는, 일반적으로 아래와 같은 포맷을 따랐다.

def bfs(x):
    visited = [0 for 0 in range(n)]
    q = [(x, 0)]
    while q:
        ~~~~ 로직

알고리즘 자체를 애초에 6개월 단기속성으로 기출문제위주로빠르게 공부하다보니 코드를 짜는 본질에 대해서는 이해도가 낮았음을 오늘 공부하면서 깨닫게 되었다. 

처음 시초가 된건 위에 적었듯이 leetcode의 bfs문제에서였다.

https://leetcode.com/explore/learn/card/queue-stack/231/practical-application-queue/1375/

요 문제를 풀려고 보는데, 카테고리가 bfs로 되어있으니 당연히 bfs문제겠거니 싶어서 몸에 익은 습관대로 위의 템플릿을 꺼내 들었다. 그런데 문제를 읽어보니 포맷이 dp같이 생겼다. 다시 읽어보니 bfs로 풀순 있었지만 문제를 풀면서 저와 비슷한 dp문제도 bfs처럼 짜서 풀수 있겠다는 생각을 했다. 위 문제의 답은 아래와 같다. 한 단어씩 위아래로 +-해보면 된다.

class Solution(object):
    def openLock(self, deadends, target):
        """
        :type deadends: List[str]
        :type target: str
        :rtype: int
        """
        visited = set()
        q = []
        deadends = set(deadends)
        if '0000' in deadends:
            return -1
        q.append([[0, 0, 0, 0], 0])
        visited.add('0000')
        while q:
            p = q.pop(0)
            if ''.join(map(str, p[0])) == target:
                return p[1]
            for order in xrange(4):
                for updown in [-1, 1]:
                    next = p[0][order] + updown
                    if next < 0:
                        next = 9
                    if next > 9:
                        next = 0
                    nextnum = p[0][:]
                    nextnum[order] = next
                    check = ''.join(map(str, nextnum))
                    if check in deadends or check in visited:
                        continue
                    q.append([nextnum, p[1] + 1])
                    visited.add(''.join(map(str, nextnum)))
        return -1

이건 특별할게 없는 bfs고, 이 바로 아래의 문제인 

https://leetcode.com/explore/learn/card/queue-stack/231/practical-application-queue/1371/

요 문제를 읽어봤는데 dp로 풀어야 할것 같은데..? 하는 생각이 들면서 bfs와 dp의 경계가 조금 무너졌다. 일단 이 문제도 동일하게 bfs로 풀수있다. (근데 아래 코드도 생각해보니 좀 헛점이 있을것같은데 test case가 완벽하지 않은지 아니면 내가 뭔가 착각하고있는지 통과는 된다.)

class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        #n = 12
        c = 1
        visited = set()
        perfect = []
        while c*c <= n:
            perfect.append(c*c)
            c += 1

        q = [[each_perfect, 1] for each_perfect in perfect]  # 모든 perfect number에 대해 조사해봐야하므로 이처럼 한데.
        while q:
            p = q.pop(0)
            if p[0] == n:
                return p[1]
            for i, each_perfect in enumerate(perfect[:]):
                nextsum = p[0] + each_perfect
                if nextsum <= n and nextsum not in visited:
                    q.append([p[0] + each_perfect, p[1] + 1])
                    visited.add(p[0] + each_perfect)

그러면서 dp에 대해서 생각을 해봤는데. dp의 요지는 한번 탐색한 값에 대해서 미리 다른곳에 저장을 해 둠으로써 동일한 값에 대해서는 탐색을 안하는게 일반적이다. 그러면 위의 bfs코드에서의 visited개념과 같지 않나..? 하는 생각을 했고. 백준에서 dp가장 처음 문제인 https://www.acmicpc.net/problem/1463를 bfs포맷으로 다시 짜보기로 했다.

짜면서 bfs와 다른점은 한번 방문했다고 방문을 안하는게 아니라, 최솟값을 저장해놔야 하므로 visited를 set이나 list가 아닌 dictionary로 만들어야한다는 것이다. 코드는 아래에 있다.

막상 짜놓고 보니 재귀적인 dp가 아니라 반복적인(바텀업) dp로 짠 코드와 상당히 유사해졌다.

def bfs(x):
    visited = dict()
    q = [(x, 0)]
    while q:
        p = q.pop(0)
        if p[0] == 1:
            return p[1]

        next = p[0]/3
        if p[0] % 3 == 0 and next not in visited:
            q.append([next, p[1] + 1])
            if next not in visited:
                visited[next] = p[1] + 1
            else:
                visited[next] = min(visited[next], p[1] + 1)

        next = p[0] / 2
        if p[0] % 2 == 0 and next not in visited:
            q.append([next, p[1] + 1])
            if next not in visited:
                visited[next] = p[1] + 1
            else:
                visited[next] = min(visited[next], p[1] + 1)

        next = p[0] - 1
        if next not in visited:
            q.append([next, p[1] + 1])
            if next not in visited:
                visited[next] = p[1] + 1
            else:
                visited[next] = min(visited[next], p[1] + 1)

x = input()
print bfs(x)

여태까지 dp를 잘 이해하지 못했다는 생각이 들었다.