코테 풀이들은 대부분 길어서 더보기 클릭을 하지 않으면 보이지 않도록 해당 문구를 추가합니다.
백준 2667: 단지번호붙이기
문제 출처 : https://www.acmicpc.net/problem/2667
문제 설명
시작점을 잡고, 해당 점에서 인접한 동서남북을 dfs 또는 bfs로 방문하면서 count하는 문제
시작 가능한 점은 지도에서 1로 표시된 구역이고, 여기서 시작하여 인접한 곳을 탐색하면 자연스럽게 단지가 정의된다.
탐색 도중 지도 밖으로 나가는 경우를 제외시켜 주어야 한다.
문제 풀이
[1] DFS
: 해당 좌표의 값이 1인 지점에서 시작하여 깊이 우선 탐색으로 단지를 정의할 수 있다. 재귀적으로 모든 인접한 구간을 방문한다.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46[풀이 논리]
1. 해당 좌표가 지도 밖이면 False
2. 해당 좌표에 집이 없으면 False
3. 해당 좌표에 집이 있는 경우, 글로벌 변수인 house_count를 1 올려주고,
4. 해당 좌표값을 0으로 만들어줌 (다시 방문하지 않기 위해)
5. 그리고 상하좌우로 dfs를 수행하여 방문함
def dfs(i,j):
if i<0 or i>N-1 or j<0 or j>N-1: # 지도 밖으로 나가면 False
return False
if array[i][j] == 0: # 집이 없으면 False
return False
else: # 집이 있는 경우 True
array[i][j] = 0 # 방문 후 0으로 만듬
global house_count
house_count += 1 # 글로별 변수에 해당 count를 누적시킴
for idx in range(4): # 인접한 곳을 재귀적으로 방문
nx, ny = i + dx[idx], j + dy[idx]
dfs(nx, ny)
return True
if __name__ == "__main__":
import sys; readline = sys.stdin.readline
N = int(readline().strip())
array = []
for _ in range(N):
array.append([int(i) for i in readline().strip()])
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
house_count, total_count = 0, 0
ans = []
for i in range(N):
for j in range(N):
if dfs(i,j): # dfs의 결과가 True인 경우 : (i,j)가 시작점 일때
ans.append(house_count)
house_count = 0 # 단지가 종료되었으므로 초기화
total_count += 1
# 결과 프린트
print(total_count)
[print(i) for i in sorted(ans)]
[2] BFS
: 해당 좌표의 값이 1인 지점에서 시작하여 넓이 우선 탐색으로 단지를 정의할 수 있다. 큐를 사용하여 인접한 좌표를 한번에 탐색한다.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
491. 집이 없는 곳은 방문하지 않음
2. 집이 있는 경우, queue를 만들고 방문 처리 후 반복문을 셋팅함
3. 반복문을 돌면서, 해당 좌표와 인접한 곳을 다 돌면서 확인함
4. 지도 밖을 넘어가지 않고, 해당 인접 좌표에 집이 있는 경우 houst_count를 올려줌.
5. 총 house_count를 리턴함. 0인 경우는 하나도 방문 못한 것이기 때문에 단지가 아님.
def bfs(i,j):
if array[i][j] == 0: # 집이 없으면 False
return 0
queue = deque([[i,j]]) # 큐에 방문 좌표 넣기
array[i][j] = 0 # 방문 처리
house_count = 1 # 현재 방문한 곳부터 세어야 함.
while queue:
x, y = queue.popleft()
for idx in range(4):
nx, ny = x + dx[idx], y + dy[idx]
if 0<=nx<N and 0<=ny<N: # 지도 밖을 넘어가지 않고,
if array[nx][ny] == 1: # 해당 좌표에 집이 있는 경우
queue.append([nx,ny]) # 큐에 넣기
array[nx][ny] = 0 # 방문 처리
house_count += 1
return house_count
if __name__ == "__main__":
import sys; readline = sys.stdin.readline
from collections import deque
N = int(readline().strip())
array = []
for _ in range(N):
array.append([int(i) for i in readline().strip()])
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
total_count = 0
ans = []
for i in range(N):
for j in range(N):
result = bfs(i,j)
if result:
ans.append(result)
total_count += 1
# 결과 프린트
print(total_count)
[print(i) for i in sorted(ans)]