안전영역(BFS)

Question

from collections import deque n = int ( input ( "n: " )) a = [[ 6 , 8 , 2 , 6 , 2 ], [ 3 , 2 , 3 , 4 , 6 ], [ 6 , 7 , 3 , 3 , 2 ], [ 7 , 2 , 5 , 3 , 6 ], [ 8 , 9 , 5 , 2 , 7 ]] dx = [ - 1 , 0 , 1 , 0 ] dy = [ 0 , 1 , 0 , - 1 ] dq = deque() for h in range ( 100 ): ch = [[ 0 ] * n for _ in range (n)] cnt = 0 res = 0 for i in range (n): for j in range (n): if ch[i][j] == 0 and a[i][j] > h: ch[i][j] = 1 dq.append((i,j)) while dq: tmp = dq.popleft() for k in range ( 4 ): x = tmp[ 0 ] + dx[k] y = tmp[ 1 ] + dy[k] if 0 <= x < n and 0 <= y < n and a[x][y] > h: ch[x][y] = 1 dq.append((x,y)) cnt += 1 res = max (cnt, res) if cnt == 0 : break print (res) BFS로 풀어봤는데 무한루프가 걸리네요. 어디 부분이 잘못됐는지 잘 모르겠습니다 ㅠㅠ

박준모 · Answer

from collections import deque n = int ( input ( "n: " )) a = [[ 6 , 8 , 2 , 6 , 2 ], [ 3 , 2 , 3 , 4 , 6 ], [ 6 , 7 , 3 , 3 , 2 ], [ 7 , 2 , 5 , 3 , 6 ], [ 8 , 9 , 5 , 2 , 7 ]] dq = deque() dx = [ - 1 , 0 , 1 , 0 ] dy = [ 0 , 1 , 0 , - 1 ] res = [] for h in range ( 1 , 101 ): ch = [[ 0 ] * n for _ in range (n)] cnt = 0 for i in range (n): for j in range (n): if ch[i][j] == 0 and a[i][j] > h: ch[i][j] = 1 dq.append((i,j)) while dq: tmp = dq.popleft() for k in range ( 4 ): x = tmp[ 0 ] + dx[k] y = tmp[ 1 ] + dy[k] if 0 <= x < n and 0 <= y < n and a[x][y] > h and ch[x][y] == 0 : ch[x][y] = 1 dq.append((x,y)) cnt += 1 if cnt > 0 : res.append(cnt) print ( max (res)) 답변 감사합니다. ch[x][y] == 0 을 추가하니까 되네요.

김태원 · Answer

첫 시작한 while dq문이 멈추지 않는 구조입니다. while문 안 if문에서 놓치고 있는게 있습니다.