[Python-CodingTest] 7-8. 사과나무 (BFS: Breadth First Search)

사과나무

문제 정리

입력

5
10 13 10 12 15
12 39 30 23 11
11 25 50 53 15
19 27 29 37 27
19 13 30 13 19

처리 과정

1. 정가운데 좌표를 큐에 넣고 탐색을 시작한다.
2. 큐에서 좌표 하나를 pop 해서 그 좌표로부터 시계 방향으로 탐색한다. (dx[],dy[] 이용)
3. 방문하지 않은 노드라면 sum에 누적, 방문 체크, 큐에 삽입한다.
4. 2~3번을 큐의 사이즈만큼 반복한다.

출력

379

풀이

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

dx=[-1,0,1,0] # 12,3,6,9시 방향
dy=[0,1,0,-1]

n=int(input())
apple=[list(map(int,input().split())) for _ in range(n)]

ch=[[0]*n for _ in range(n)] # 방문한 노드 체크
sum=0
Q=deque() # Q에서 pop한 좌표를 기준으로 시계방향 탐색

ch[n//2][n//2]=1 # 정가운데(n//2,n//2)부터 방문
sum+=apple[n//2][n//2]
Q.append((n//2,n//2)) # 시작점을 큐에 넣어놓고 BFS 시작 
L=0

while True:
    if L==n//2: # 목표 지점까지 온 것
        break
    size=len(Q)
    for _ in range(size): # Q의 사이즈만큼 돌기
        cur=Q.popleft()
        for j in range(4): # 시계 방향으로 돌면서 탐색
            x=cur[0]+dx[j] # cur[0]은 튜플의 x값
            y=cur[1]+dy[j] # cur[1]은 튜플의 y값
            if ch[x][y]==0: # 방문하지 않은 노드일 때만
                sum+=apple[x][y]
                ch[x][y]=1
                Q.append((x,y)) # 튜플값으로 Q에 삽입
    L+=1
print(sum)

정리

• 시계 방향으로 탐색할 때는 dx=[-1,0,1,0]와 dy=[0,1,0,-1] 이용!
• while문의 종료 지점은 L==n//2이다.

---

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

맨 위로 이동하기