[백준 2667] 단지번호붙이기 (BFS 풀이)

제약 조건

 

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

예제

---

나의 풀이

이 문제는 전형적인 DFS 혹은 BFS 문제이다.

2021.06.26 - 깊이 우선 탐색(DFS, Depth First Search) 파이썬 구현

깊이 우선 탐색(DFS, Depth First Search) 파이썬 구현

2021.05.23 - 너비 우선 탐색(BFS, Breadth First Search) 파이썬 구현

너비 우선 탐색(BFS, Breadth First Search) 파이썬 구현

 

이 문제와 비슷한 유형의 문제가 있었다. 바로 프로그래머스 위클리 챌린지 3주차 문제였다.

프로그래머스 문제가 훨씬 어려운 문제니 이 글을 보고 프로그래머스 문제도 풀어볼 것을 권장한다.

(프로그래머스 문제 풀 때는 DFS로 풀었지만 이번 백준 문제는 BFS로 풀었다. 즉, 둘 다 가능하다는 말이다. 기존에 DFS로 풀었다면 BFS로, BFS로 풀었다면 DFS로도 풀어볼 것을 추천한다)

2021.08.17 - [프로그래머스 위클리 챌린지 (lv3)] 3주차_퍼즐 조각 채우기 (DFS)

[프로그래머스 위클리 챌린지 (lv3)] 3주차_퍼즐 조각 채우기 (DFS)

 

---

소스코드

from collections import deque

def bfs(x, y):
    if graph[x][y]=='0' or visited[x][y]: return
    dx = [1, -1, 0, 0]
    dy = [0, 0, -1, 1]
    queue = deque([(x, y)])
    visited[x][y] = True
    count = 0
    while queue:
        x, y = queue.popleft()
        count += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and graph[nx][ny]=='1':
                queue.append((nx, ny))
                visited[nx][ny] = True
    counts.append(count)

n = int(input())
graph = [input() for _ in range(n)]
visited = [[False] * n for _ in range(n)]
counts = []
for i in range(n):
    for j in range(n):
        bfs(i, j)
print(len(counts))
for c in sorted(counts):
    print(c)

입력 받은 지도에서 0이거나 이미 방문했던 장소는 return 하여 바로 빠져나온다.

방문하지 않았던 주변 집에 대하여 큐에 추가하고 방문처리를 한다.

하나의 집을 처리할 때마다 개수를 더해주고, while문이 끝나면 연결된 단지를 구할 수 있게 된다. 여기서는 개수만 세면 되므로 count한 값을 counts라는 리스트에 추가한다.

모든 경우에 대해 bfs()를 돌리면 counts에는 단지에 포함된 집들의 개수 리스트가 들어간다.

문제의 요구 사항에 따라 단지의 개수와 각 단지에 포함된 집 개수를 오름차순으로 정렬하여 출력하면 정답이 된다.

 

채점 결과