잘 풀은 것 같은데 틀렸습니다. 가 출력되는 분들이 보면 좋을 것 같다.
정답 코드
from collections import deque
def bfs(x, y):
queue = deque([(x, y)])
count = 0
graph[x][y] += 1
while queue:
x, y = queue.popleft()
count += 1
for i in range(4):
nx = dx[i] + x
ny = dy[i] + y
if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
return count
n = int(input())
graph = [list(map(int, input())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
apart = 0
result = []
for i in range(n):
for j in range(n):
if graph[i][j] == 1:
result.append(bfs(i, j))
apart += 1
print(apart)
for i in sorted(result):
print(i)풀이 과정
이전에 dfs로 풀었던 것 같은데 bfs로 풀이했다.
같다 뭐 너비우선탐색을 하면서 1이 있으면 카운팅을 해주면 된다.
상하좌우를 탐색하며 1인게 없으면 중단
틀렸습니다 이유
https://www.acmicpc.net/board/view/141602
질문 게시판을 한번 보았는데 이 분께서 적어주신 테스트케이스를 출력하자 역시 0만 나왔다.
단지로 계산했기 때문에 주변에 1이 있으면 카운팅을 해주었는데 주변에 아무것도 없이 하나만 덩그러니 놓여있어도 단지로 취급하는 것을 파악했다.
그래서 저 해당 조건에 속할 때만 카운팅을 하는 것이 아니라 while문을 돌때 전부 카운팅을 했다.
def bfs(x, y):
queue = deque([(x, y)])
count = 0
graph[x][y] += 1
while queue:
x, y = queue.popleft()
count += 1
for i in range(4):
nx = dx[i] + x
ny = dy[i] + y
if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
return count
돌 때마다 카운팅을 했고 중복을 제거하기 위해 visited를 사용하면 좋으나 사용하기 귀찮아서 안했다.
그래서 처음 bfs에 들어오면 바로 += 1을 해서 1이 아닌 값으로 바꿔버렸다.
이미 방문했다는 뜻이고 이는 처음 while문으로 들어가자마자 첫 카운트가 더해진다.
그리고 주변에 단지가 없으니까 추가적인 while문은 돌지 않아 정상적으로 출력된다.
풀이 후기
쉬웠다. 연속으로 BFS만 4문제를 푸니까 감이 좀 잡힌다.
