BFS 백준 - 2667 [Python]

Problem)

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

2667번: 단지번호붙이기

Solution)

이 문제같은 경우에는, 인접리스트로 굳이 풀 필요가 없다. 왜냐하면 i행 j열을 알고있을 경우, 인접한 부분은 상,하,좌,우 밖에 없기 때문이다. 

따라서 이 문제의 경우, 정점의 경우 정수 2개의 조합으로 문제를 해결하면 된다.

• d[i][j] = (i,j)를 방문안했으면 0 했으면 단지번호를 넣는다.

Answer)

from collections import deque, Counter
from functools import reduce

dx = [0,0,1,-1]
dy = [1,-1,0,0]

def dfs(x,y,cnt):
    group[x][y] = cnt
    for k in range(4):
        nx, ny = x+dx[k], y+dy[k]
        
        if 0<=nx <n and 0<=ny <n:
            if a[nx][ny] == 1 and group[nx][ny] == 0:
                dfs(nx,ny,cnt)
    
    
n = int(input())
a = [list(map(int,list(input()))) for _ in range(n)]
group = [[0]*n for _ in range(n)]
cnt = 0

for i in range(n):
    for j in range(n):
        if a[i][j] == 1 and group[i][j] == 0:
            cnt+=1
            dfs(i,j,cnt)
            
ans = reduce(lambda x,y: x+y, group)
ans = [x for x in ans if x>0]
ans = sorted(list(Counter(ans).values()))
print(cnt)
print('\n'.join(map(str,ans)))