[Python-CodingTest] 7-7. 송아지 찾기 (BFS: Breadth First Search)

송아지 찾기

문제 정리

입력

5 14

처리 과정

1. 큐를 생성한다.
2. 출발지로부터의 거리(dis[])와 중복체크(ch[]) 리스트를 각각 0과 1로 초기화한다.
3. 큐에서 하나(=cur)를 pop 해서 방문한 뒤에, 거기서부터 -1, +1, +5인 지점을 큐에 넣고 순서대로 방문한다.
4. 3번을 반복하며 출발지로부터의 거리(dis[]) 리스트를 채운다.
5. cur이 m이 되었을 때 출발지로부터의 거리(dis[m])을 출력한다.

출력

3

풀이

import sys
from collections import deque
sys.stdin = open("./input/in7.txt", "rt")

MAX=10000 # 좌표의 최대값
ch=[0]*(MAX+1) # 중복 체크 리스트 - 더 멀리 돌아가는 것 방지
dis=[0]*(MAX+1) # 거리(distance)

n,m=map(int,input().split())
ch[n]=1 # 방문한 노드는 1로
dis[n]=0

dQ=deque() # 큐 생성
dQ.append(n)

while dQ:
    cur=dQ.popleft() # 현재 방문한 노드
    if cur==m:
        break
    for i in(cur-1, cur+1, cur+5): # for문이 3번 돎 # next는 다음에 방문할 노드
        if 0<i<MAX:
            if ch[i]==0: # 방문하지 않았을 때만
                dQ.append(i)
                ch[i]=1
                dis[i]=dis[cur]+1 # 거리는 부모(dis[cur])로 부터 1 증가
print(dis[m]) # m까지 몇 번만에 가는지 

정리

• for i in(1,3,7):: i가 1,3,7일 때 (총 세 번 반복한다)
• Q.popleft(): 큐에서 원소 pop하기
• Q.append(): 큐에 원소 집어넣기

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기