공부 자료/알고리즘
(Python/파이썬) 백준 2667번 - 단지번호붙이기
뚜루뚜루세니
2021. 9. 8. 17:18
728x90
문제출처: https://www.acmicpc.net/problem/2667
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여
www.acmicpc.net
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
|
#dfs
#인접한 곳에 1이 있으면 그 점에서 다시 인접한 곳 탐색
#탐색할 때마다 카운트 세주고, 탐색 끝나면 정답 저장
n= int(input())
graph =[]
for _ in range(n): #자료 입력
graph.append(list(map(int,input())))
ans=[]
cnt =0
#상하좌우
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def dfs(x,y):
global cnt
if x<0 or x>= n or y<0 or y>=n: # 범위
return False
if graph[x][y]==1:
cnt +=1
graph[x][y] = 0
for i in range(4):
dfs(x+dx[i],y+dy[i])
return True
for i in range(n):
for j in range(n):
if dfs(i,j)==True:
ans.append(cnt)
cnt = 0
print(len(ans))
ans.sort()
for i in ans:
print(i)
|
cs |
2. 해결과정
그래프 탐색 문제였다. 동서남북에 인접한 곳에 집이 있으면 (= 값이 1이라면) 집이 연결되어 있다고 하고, 연결된 집의 모임을 단지라고 한다. 단지의 개수, 각 단지 내 에서의 집의 수를 출력해주면 된다.
어느 한 점에 대해서 인접한 곳에 1이 있는지 탐색하고, 1이 있다면 그 점에서 다시 인접한 곳을 탐색하는 것을 반복해주고, 탐색을 할 때마다 카운트를 세다가 끝나면, 카운트 값을 정답에 저장해주면 된다.
dfs로 풀어줬는데, 그래프의 탐색 시작점을 모르기 때문에 전체를 돌면서 1인 지점에서 탐색을 시작해주면 되고, 재귀를 사용하여 풀수 있었던 문제였다.
3. 느낀점
현재는 dfs로 풀어줬는데, 다음에는 bfs로 풀어봐야겠다고 생각했다. 이 파트가 좀 약한 것 같다는 생각이 들었다.
728x90