[백준 문제] 2667번 단지번호붙이기 (파이썬)
[백준 문제] 2667번 단지번호붙이기 (파이썬)
문제풀이
- BFS로 풀었는데 다음에는 DFS로도 풀어보려한다.
- 두가지만 기억하면 되는데 먼저 첫 시작점을 찾고, 그 시작점에서 BFS로 단지번호를 물들인다. 또 시작점 찾고 물들인다. 이렇게 풀면된다.
# 데이터 입력
n = int(input())
a = [list(map(int,list(input()))) for _ in range(n)]
d = [[0]*n for _ in range(n)]
# cnt(단지번호)와 dx, dy로 이루어진 아래 위 오른 왼 방향
cnt = 0
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
# bfs를 이용해서 싹 다 그 단지번호로 지정해주기
def bfs(x, y, cnt) :
d[x][y] = cnt;
queue = [[x,y]]
while queue :
current_node = queue.pop(0)
for k in range(4) :
nx = current_node[0]+dx[k] ;
ny = current_node[1]+dy[k] ;
if (0 <= nx and nx < n) and (0 <= ny and ny < n) :
if a[nx][ny] == 1 and d[nx][ny] == 0 :
queue += [[nx, ny]] ;
d[nx][ny] = cnt
# 첫 지역을 찾아서 bfs로 단지번호 지정해주고 또 다음 지역을 찾아서 지정해주는식
for i in range(n) :
for j in range(n) :
if a[i][j] == 1 and d[i][j] == 0 :
cnt += 1
bfs(i, j, cnt)
# 2차원을 1차원 리스트로 바꿔주기
answer = []
for i in d :
answer += i
# 답 구해주기 (총 단지수랑 단지의 수를 sorting해서 출력하기)
print(max(answer))
arr = []
for x in range(1,max(answer)+1) :
sum = 0
for i in answer :
if x == i :
sum += 1
arr.append(sum)
for _ in range(max(answer)) :
arr.sort()
for i in arr :
print(i)
3
7
8
9
# 얘는 그냥 잘 되었나 찍어보기~
d
[[0, 1, 1, 0, 2, 0, 0],
[0, 1, 1, 0, 2, 0, 2],
[1, 1, 1, 0, 2, 0, 2],
[0, 0, 0, 0, 2, 2, 2],
[0, 3, 0, 0, 0, 0, 0],
[0, 3, 3, 3, 3, 3, 0],
[0, 3, 3, 3, 0, 0, 0]]