[python] SWEA 5247 : 연산 (BFS)

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

1. 코드 구현 (방문처리시 dict 사용) 

from collections import deque

def bfs():
    que = deque([(N, 0)])
    dic = dict()
    while que:
        now, count = que.popleft()
        # 해당 숫자를 이미 방문한 경우
        if dic.get(now, 0): continue
        # 방문하지 않는 숫자인 경우
        dic[now] = 1
        if now == M:
            return count
        count += 1
        if 0 < now - 1 <= 10**6:
            que.append((now-1, count))
        if 0 < now + 1 <= 10**6:
            que.append((now+1, count))
        if 0 < now * 2 <= 10**6:
            que.append((now*2, count))
        if 0 < now - 10 <= 10**6:
            que.append((now-10, count))


for tc in range(1, int(input())+1):
    N, M = map(int, input().split())
    result = bfs()
    print(f'#{tc} {result}')

 

2. 코드 구현 (방문처리시 배열 사용) 

from collections import deque

def bfs():
    que = deque([(N, 0)])
    visited = [0]*(10**6+1)
    while que:
        now, count = que.popleft()
        # 해당 숫자를 이미 방문한 경우
        if visited[now]:
            continue
        # 방문하지 않는 숫자인 경우
        visited[now] = 1
        if now == M:
            return count
        count += 1
        if 0 < now - 1 <= 10**6:
            que.append((now-1, count))
        if 0 < now + 1 <= 10**6:
            que.append((now+1, count))
        if 0 < now * 2 <= 10**6:
            que.append((now*2, count))
        if 0 < now - 10 <= 10**6:
            que.append((now-10, count))


for tc in range(1, int(input())+1):
    N, M = map(int, input().split())
    result = bfs()
    print(f'#{tc} {result}')

 

3. 코드 구현 (방문처리시 set 사용)

from collections import deque

def bfs():
    que = deque([(N, 0)])
    visited = set()
    while que:
        now, count = que.popleft()
        # 해당 숫자를 이미 방문한 경우
        if now in visited:
            continue
        # 방문하지 않는 숫자인 경우
        visited.add(now)
        if now == M:
            return count
        count += 1
        if 0 < now - 1 <= 10**6:
            que.append((now-1, count))
        if 0 < now + 1 <= 10**6:
            que.append((now+1, count))
        if 0 < now * 2 <= 10**6:
            que.append((now*2, count))
        if 0 < now - 10 <= 10**6:
            que.append((now-10, count))


for tc in range(1, int(input())+1):
    N, M = map(int, input().split())
    result = bfs()
    print(f'#{tc} {result}')

 

[BFS를 이용하여 문제 접근]

BFS : 루트 노드부터 시작하여 인접한 노드를 먼저 탐색하는 방법 (깊이가 같은 너비의 노드를 먼저 탐색)

- 두 노드 간 최소 경로를 구하는 성질이 있다.

- '최소 몇번', '최단 경로', '최소 연산 횟수'와 같은 표현이 사용된 문제에 주로 사용된다. 

- DFS(깊이우선탐색) 보다 빠름

- 방문한 노드를 차례대로 꺼낼 수 있도록 queue 사용 

 

 

* 유사한 문제 : 백준 숨바꼭질 

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질