[백준]2667번 단지번호붙이기 (Python/파이썬)

2024.04.11 - [코딩테스트] - [백준]2178번 미로탐색 (Python/파이썬) - BFS 코테 문제

1. 문제 설명

1) 문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 

1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 

철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 

여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 

대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 

지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

 

그림 2와 같이, 상하좌우로 연결된 1의 그룹을 하나의 단지로 정의한다.

 

2) 입/출력

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

 

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

 

> 예제 입력

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

 

> 예제 출력

3
7
8
9

 

3) 알고리즘

임의의 시작 노드에서 상하좌우에 위치한 노드의 값이 1인 경우, 몇 칸을 이동해야 하는지를 구하는 2178번 미로탐색 문제와 유사하게 풀이가 가능합니다.

2024.04.11 - [코딩테스트] - [백준]2178번 미로탐색 (Python/파이썬) - BFS 코테 문제

[백준]2178번 미로탐색 (Python/파이썬) - BFS 코테 문제

 

저는 2178번 문제를 너비 우선 탐색(Breadth-First Search, BFS)으로 구현했었는데, 이 문제는 임의의 시작하는 노드가 (0,0)에 한정되지 않는다는 점에서 차이가 있습니다.

 

처음에는 (0,0), (0,N-1), (N-1, 0), (N-1,N-1) 네 가지 모서리에서 탐색을 시작하는 방식으로 코드를 짰는데, 주어진 예제에서는 맞았지만 hidden test case에 대해서는 오답이었습니다.

 

아래와 같이, BFS를 시작하는 노드가 전체 노드일 수 있도록 main 부분을 구현해야 합니다.

---

2. 구현 코드

1) 2178번과 유사한 구현

from collections import deque

def bfs(graph, visited, i, j):
    need_visited = deque([])
    need_visited.append((i, j))
    visited[i][j] = True

    # 상하좌우 탐색
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    num_apt = 1

    while need_visited:
        x, y = need_visited.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue

            if visited[nx][ny] == False and graph[nx][ny] == '1':
                need_visited.append((nx, ny))
                visited[nx][ny] = True
                num_apt += 1

    return num_apt


N = int(input())
graph = []
for i in range(N):
    nodes = list(input())
    graph.append(nodes)

visited = [[False for _ in range(N)] for _ in range(N)]
apt_num = []
for i in range(N):
    for j in range(N):
        # visited 함께 체크해야 test case 모두 통과 가능
        if graph[i][j] == '1' and visited[i][j] == False:
            apt_num.append(bfs(graph, visited, i, j))

apt_num.sort()
print(len(apt_num))
for num in apt_num:
    print(num)

 

이때, 그래프 내에서 '1'(이동 가능)인지와 함께, visited가 False(처음 방문하는 노드인지)도 체크해줘야 test case에서 모두 통과할 수 있습니다.

 

추가로, visited를 global variable로 하지 않을 것이기 때문에, 함수의 input parameter로 설정해주었습니다.

이렇게 하지 않고 함수 내에서 선언하게 되면 이전의 방문 기록이 사라져 다시 방문하게 될 수 있습니다.

 

2) 참고 코드

https://hongcoding.tistory.com/71

[백준] 2667 단지번호붙이기 (Python 파이썬)

 

visited matrix를 별도로 선언하지 않고, 더 간단하게 구현할 수 있는 방법을 찾았습니다.

방문한 노드에 대해, 입력 graph 자체에서 '1'(이동 가능)을 '0'(이동 불가)으로 수정할 경우, 중복되어 카운트되지 않습니다.

이 때문에 main 부분에서 visited가 False(처음 방문하는 노드인지) 체크하는 if 문이 사라지기 때문에 코드 가독성이 더 좋습니다.

 

from collections import deque

def bfs(graph, i, j):
    N = len(graph)
    need_visited = deque([])
    need_visited.append((i, j))

    graph[i][j] = '0'
    num_apt = 1

    # 상하좌우 탐색
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    while need_visited:
        x, y = need_visited.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue

            if graph[nx][ny] == '1':
                need_visited.append((nx, ny))
                graph[nx][ny] = '0'
                num_apt += 1

    return num_apt


N = int(input())
graph = []
for i in range(N):
    nodes = list(input())
    graph.append(nodes)

cnt = []
for i in range(N):
    for j in range(N):
        if graph[i][j] == '1':
            cnt.append(bfs(graph, i, j))

cnt.sort()
print(len(cnt))
for c in cnt:
    print(c)

---

문제 출처

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기