-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
단지번호붙이기 BFS로 문제해결관련
21.09.03 14:35 작성 조회수 120
0
안녕하세요 강사님
chap7에서 단지번호붙이기를 BFS로 해결해보았는데 문제내 입력예제와 출력예제는 제대로 해결이 되지만 채점파일에있는 3,4,5예제에서는 틀리게 답이 나타나는데 코드에서의 원인을 찾지 못해서 질문드립니다.
import sys sys.stdin = open('input.txt','rt') from collections import deque n = int(input()) board = [list(map(int,input())) for _ in range(n)] ch = [[0]*n for _ in range(n)] res = [] dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] Q = deque() for i in range(n): for j in range(n): if board[i][j] == 1: #for y in board: #print(y) #print() board[i][j] = 0 cnt = 1 Q.append((i,j)) while Q: for j in range(len(Q)): x,y = Q.popleft() for i in range(4): xx = x + dx[i] yy = y + dy[i] if 0<=xx<n and 0<=yy<n and board[xx][yy]==1: board[xx][yy]=0 cnt += 1 Q.append((xx,yy)) res.append(cnt) print(len(res)) res.sort() for x in res: print(x)
코드에 문제가 있는 부분에 대해 알려주시길 부탁드립니다.
답변을 작성해보세요.
0
김태원
지식공유자2021.09.05
안녕하세요^^
i, j 변수를 하위 블록에서 중복해서 사용하면 안됩니다.
아래와 같이 큐를 돌리시면 됩니다.
while Q:
for _ in range(len(Q)):
x,y = Q.popleft()
for k in range(4):
xx = x + dx[k]
yy = y + dy[k]
if 0<=xx<n and 0<=yy<n and board[xx][yy]==1:
board[xx][yy]=0
cnt += 1
Q.append((xx,yy))
res.append(cnt)
답변 1