출처 : https://www.acmicpc.net/problem/2667
난이도 : 실버 1
문제 이해
크기가 N x N인 정사각형 지도가 주어진다.
지도는 0과 1로 이루어져 있으며,
- 0: 집이 없는 곳
- 1: 집이 있는 곳
을 의미한다.
여기서 상하좌우로 연결된 집들의 묶음을 하나의 단지라고 한다.
대각선 방향은 연결된 것으로 보지 않는다.
구해야 하는 것은 다음 두 가지이다.
- 총 단지의 개수
- 각 단지에 속한 집의 수를 오름차순으로 정렬한 결과
해결 아이디어
이 문제는 그래프 탐색 문제이다.
특정 위치의 집과 연결된 모든 집을 한 번에 묶어서 탐색해야 하므로 DFS를 사용하면 자연스럽게 해결할 수 있다.
지도를 처음부터 끝까지 순회하다가 값이 1인 위치를 발견하면,
그 지점에서 DFS를 시작해 연결된 모든 집을 방문한다.
DFS가 한 번 시작될 때마다 새로운 단지를 하나 찾은 것이고,
탐색 과정에서 방문한 집의 수를 세면 해당 단지의 크기도 함께 구할 수 있다.
탐색이 끝난 집은 다시 세지 않도록 0으로 바꿔 처리했다.
정리하면 흐름은 다음과 같다.
- 전체 지도를 순회한다.
- 집이 있는 칸(1)을 발견하면 DFS를 시작한다.
- DFS로 연결된 모든 집을 방문하며 개수를 센다.
- DFS가 끝나면 그 개수를 결과 배열에 저장한다.
- 모든 탐색이 끝난 뒤 결과 배열을 오름차순 정렬해 출력한다.
핵심 포인트
1. 단지 개수는 DFS를 시작한 횟수다
아직 방문하지 않은 집을 발견했다는 것은
새로운 단지를 처음 만났다는 뜻이다.
그래서 1을 만날 때마다 DFS를 호출하고,
그 호출 횟수만큼 단지가 존재한다고 볼 수 있다.
2. 단지 내 집 수는 DFS가 방문한 칸의 개수다
현재 위치를 방문할 때마다 count를 1씩 증가시키고,
상하좌우로 연결된 집을 계속 재귀적으로 탐색하면
해당 단지의 전체 집 수를 구할 수 있다.
3. 방문 처리는 값을 0으로 바꿔서 해결한다
별도의 visited 배열 없이
방문한 집을 바로 0으로 바꾸면 중복 탐색을 막을 수 있다.
풀이 코드
import sys
input = sys.stdin.readline
N = int(input())
graph = []
for _ in range(N):
graph.append(list(map(int, input().strip())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def dfs(x, y):
if x < 0 or x >= N or y < 0 or y >= N:
return 0
if graph[x][y] == 0:
return 0
graph[x][y] = 0
count = 1
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
count += dfs(nx, ny)
return count
result = []
for i in range(N):
for j in range(N):
if graph[i][j] == 1:
result.append(dfs(i, j))
result.sort()
print(len(result))
for r in result:
print(r)코드 설명
입력 처리
N = int(input())
graph = []
for _ in range(N):
graph.append(list(map(int, input().strip())))N x N 형태의 지도를 입력받는다.
각 줄이 공백 없이 주어지므로 input().strip()으로 문자열을 받은 뒤,
각 문자를 정수로 변환해 리스트로 저장한다.
방향 벡터
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]상하좌우 네 방향으로 이동하기 위한 배열이다.
- (-1, 0): 위
- (1, 0): 아래
- (0, -1): 왼쪽
- (0, 1): 오른쪽
DFS 함수
def dfs(x, y):
if x < 0 or x >= N or y < 0 or y >= N:
return 0
if graph[x][y] == 0:
return 0
graph[x][y] = 0
count = 1
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
count += dfs(nx, ny)
return count이 함수는 현재 위치에서 시작해서 연결된 모든 집의 개수를 반환한다.
먼저 범위를 벗어나면 더 이상 탐색할 수 없으므로 0을 반환한다.
또한 현재 위치가 0이라면 집이 없는 곳이거나 이미 방문한 곳이므로 역시 0을 반환한다.
현재 위치가 집이라면 방문 처리로 0으로 바꾸고,
현재 집 하나를 포함하므로 count를 1로 시작한다.
이후 상하좌우 네 방향에 대해 DFS를 호출하고,
그 결과를 모두 더해 현재 단지의 총 집 수를 구한다.
전체 탐색
result = []
for i in range(N):
for j in range(N):
if graph[i][j] == 1:
result.append(dfs(i, j))지도를 끝까지 순회하면서 아직 방문하지 않은 집을 발견하면 DFS를 실행한다.
DFS의 반환값은 해당 단지의 집 수이므로 result에 저장한다.
정렬 및 출력
result.sort()
print(len(result))
for r in result:
print(r)문제에서 각 단지의 집 수를 오름차순으로 출력하라고 했으므로 정렬한 뒤 출력한다.
result의 길이는 단지의 개수와 같다.
느낀 점
이 문제는 DFS의 기본 구조를 연습하기에 정말 좋은 문제였다.
특히
- 방향 벡터를 활용한 2차원 탐색
- 재귀 DFS의 흐름
- 방문 처리 방식
- 연결 요소의 개수를 세는 방법
을 한 번에 익힐 수 있었다.
단순히 탐색만 하는 것이 아니라,
DFS 한 번으로 단지 하나의 크기까지 같이 구할 수 있다는 점이 핵심이었다.
그래프 탐색 기본기를 다지기에 좋은 문제였다.
