송아지 찾기

it 취업을 위한 알고리즘 문제 풀이

문제

코드

import sys
from collections import deque
#sys.stdin = open("input.txt","rt")
cnt = 0
dir = [5,-1,1]
def bfs(s,e,visited):
    global cnt
    global dir
    queue = deque()
    queue.append((s,0))
    visited[s] = True

    while queue:
        x, cnt = queue.popleft()
        cnt += 1
        for i in dir:
            nx = x + i
            if nx == e:
                return 
            if nx<0 or nx>10000: continue
            if visited[nx]:continue
            queue.append((nx,cnt))
            visited[nx] = True



s,e = map(int,input().split())
visited = [False]*10001

bfs(s,e,visited)
print(cnt)

문제해결방법

• 최소횟수를 찾으라고 했을 때 BFS알고리즘을 활용하면 좋다. 횟수를 그래프에서 레벨로 정의하고 각 레벨마다 이동가능한 좌표를 정점으로하는 그래프를 생각했을 때, 가장 가까운 레벨들을 탐색하면서 원하는 지점에 도착했는지를 체크하면서 그래프 탐색을 진행할 때 원하는 지점에 도착하면 그때의 레벨이 최소 이동 횟수이다. 이렇게 BFS는 가장 인접한 레벨의 정점을 먼저 탐색하는 알고리즘인데 가장 인접한 곳에서 원하는 정점이 나오지 않았다면 다음 레벨을 체크하는데 그곳에서 발견이 된다면 그 레벨보다 더 이전 레벨에는 원하는 정점이 없었다는 이야기이고 그 이후 레벨에서 발견되는 것은 최소횟수가 아니기 때문에 이러한 문제를 풀때 BFS를 활용하면 좋다.
• BFS 알고리즘을 활용하기 위해 방문한 방문한 정점과 레벨의 정보를 튜플 자료구조로 큐에 넣어주었다. 그리고 큐가 빌 때까지 자료를 꺼내주어 현재 꺼내진 좌표에서 이동가능한 +5,+1,-1 정점을 새로운 좌표로 그래프에 정점으로 만들어주고 이전 레벨에서 +1을 해주어 정점의 정보와 레벨 정보를 큐에 넣어준다. 이때 정점의 정보가 이미 방문했거나 문제의 주어진 범위를 벗어 난다면 방문할 필요가 없기 때문에 큐에 넣어주지 않는다.
• 이렇게 다음 좌표를 구하면서 다음 좌표가 문제의 end좌표이면 return을 해주고 그때 까지 이동한 횟수를 출력해주면 된다.