[백준] 2667 단지 번호 붙이기 파이썬 풀이 (DFS, BFS)

 

---

코드

import sys

dx=[-1,0,1,0]
dy=[0,1,0,-1]
n=int(sys.stdin.readline())
a=[list(sys.stdin.readline()) for _ in range(n)]
print(a)
cnt=0
apt=[]

def dfs(x,y):
    global cnt
    a[x][y] = '0' #방문한 곳은 0으로 바꾼다.
    cnt+=1
    for i in range(4):
        nx = x + dx[i] #설명
        ny = y + dy[i]
        if nx < 0 or nx >= n or ny < 0 or ny >=n:
            continue
        if a[nx][ny] == '1':
            dfs(nx,ny)

for i in range(n):
    for j in range(n):
        if a[i][j] == '1':
            cnt= 0
            dfs(i,j)
            apt.append(cnt)

print(len(apt))
apt.sort()
for i in apt:
    print(i)

 

 

 

 

풀이

1.

전체를 돌면서 1이 나오는지 확인

1이 나오면 dfs를 호출해서 양옆 위아래가 뭔지 확인

 

 

2.

방문한 곳은 1을 0으로 바꾼다.

이 dfs를 호출할때마다 count를 +1해준다.

(연결되어있는 것만 count된다. 이 dfs가 끝나면 apt에 여기서 만들어진 cnt를 append하고

다시 이중 for문을 돌면서 1이 있는 것을 찾으면 다시 cnt가 0으로 시작되기 때문)

 

한 점을 기준으로 4방을 비교 하려고 dx와 dy리스트를 만들었다.

dx에서보면 x좌표가 -1간것, 그대로인것, +1인것 , 그대로인 것이고

dy를 보면 y좌표가 그대로인것, +1인것, 그대로인것, -1인것이다.

dx와 dy를 같은 인덱스 끼리 합쳐보면

[0]은 x좌표가 -1, y좌표는 그대로 -> a[x-1][y] -> 위

[1]은 x좌표 그대로, y좌표는 +1 -> a[x][y+1] -> 오른쪽

[2]는 x좌표 +1, y좌표 그대로 -> a[x+1][y] -> 아래

[3]은 x좌표는 그대로, y좌표는 -1 -> a[x][y-1] -> 왼쪽

 

그래서 그 점 기준으로 4번을 돌면서 왼 위 오 아래가 1인지 확인한다.

그런데 x좌표와 y죄표가 범위를 벗어나면 continue를 한다.

1이 있는게 없으면 dfs함수가 끝나고

apt에 append된다.

 

그렇게 apt의 길이가 단지의 수가 되고

apt의 원소에 담긴 숫자들이 단지마다 아파트 수를 의미한다.