[Python][백준/BOJ] 2667번 : 단지번호붙이기

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

2667번: 단지번호붙이기

 

내 코드

import sys
input = sys.stdin.readline

n = int(input())
dx = [1,-1,0,0]
dy = [0,0,1,-1]

cnt =0
board =[list(map(int,input().rstrip())) for _ in range(n)]
visited = []*(n+1)

ans = []
result =0
def dfs(x, y):

    if x <0 or x>=n or y<0 or y>=n:
        return
    
    if board[x][y] == 1:
        global cnt
        cnt+=1
        board[x][y]=0
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            dfs(nx,ny)
        return True
    return False
        
            
for i in range(n):
    for j in range(n):
        if dfs(i,j) == True:
            ans.append(cnt)
            result +=1
            cnt =0
        
ans.sort()
print(result)
print("\n".join(map(str, ans)))

 

DFS, 이어져 있는 수들의 개수 세기

일반적인 DFS 풀이와 같지만, 이어져 있는 수를 한 번에 세고나서 이미 센 곳은 0으로 바꾼다.

1만 찾아가는 DFS 풀이이기 때문에 VISITED가 따로 필요없다.

        return True   
return False

나는 구글링하다가 끝에 있는 이 부분이 궁금했는데, 

return True는 어차피 if문이 1일때 동작하는 것이므로 신나게 한 바퀴 다 돌고 나서 밑에 있는 dfs(i,j)==True에게 True라는 것을 전달하는 역할이다.

return False는 0인 좌표를 마주쳤을 때 반환하는 False 값이다.이 두 return은 

for i in range(n):
    for j in range(n):
        if dfs(i,j) == True:
            ans.append(cnt)

이 부분에서 유용하게 사용된다.

 

' '.join(list)

그리고 여기서 한 번 더 막혔는데, 이는 ' '.join()이 리스트 값이면 무조건 반환 가능하다고 생각했기 때문이다.

' '.join()은 str 자료형에서만 가능하다. 

그래서 만약 list의 구성이 int로 되어있을 경우에는 str로 바꿔주어야 한다.

print("\n".join(map(str, ans)))