[Python] 백준 1697번 숨바꼭질 (DFS/BFS)

문제 풀이 1

• 큐에 수빈이의 좌표와 이동하는 데 걸린 시간을 삽입하여 bfs 탐색

코드

from collections import deque
subin, destination = map(int, input().split())
max_num = 100000
visited = [0] * (max_num + 1)

def bfs():
    queue = deque()
    queue.append((subin, 0))
    visited[subin] = 1
    while queue:
        x, count = queue.popleft()
        if x == destination:
            visited[x] = 1
            return count
        else:
            for i in (x + 1, x - 1, x * 2):
                if 0 <= i <= max_num and not visited[i]:
                    visited[i] = 1
                    queue.append((i, count + 1))

print(bfs())

 

문제 풀이 2

• 방문 처리 할 때 초를 카운트 해서 값을 넣은 후, 좌표가 같아졌을 때의 값 출력

코드

from collections import deque
n, m = map(int,input().split())
max_num = 100000
visited = [0] * (max_num + 1)
def bfs():
    queue = deque()
    queue.append(n)
    while queue:
        x = queue.popleft()
        if x == m:
            return visited[x]
        else:
            for i in (x - 1, x + 1, x * 2):
                if 0 <= i <= max_num and visited[i] == 0:
                    visited[i] = visited[x] + 1
                    queue.append(i)
print(bfs())

오답 코드

import sys
from collections import deque

sub, sis = map(int,sys.stdin.readline().split())
def bfs(sub, sec):
    queue = deque()
    # 수빈이의 위치와 시간 초 삽입
    queue.append((sub, sec))
    while queue:
        sub_loc, sec = queue.popleft()
        # 동생 위치에 도달하면 시간 리턴
        if sub_loc == sis:
            return sec

        for i in [sub_loc + 1, sub_loc -1, 2 * sub_loc]:
            queue.append((i, sec + 1))

print(bfs(sub,0))

•  방문처리 하지 않고, 좌표와 시간 초만 삽입할 때 메모리 초과가 떴다.
• 계속해서 같은 숫자를 삽입하게 되는 경우가 생겨, 꼭  방문처리를 하며 탐색 해야한다