[백준/파이썬]2667 단지 번호 붙이기

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

2667번: 단지번호붙이기

 

문제

백준 2667번 단지 번호 붙이기

DFS혹은 BFS로 풀면 되는 문제다!

 

아직 BFS를 어떻게 짜야하는지 잘 모르므로 DFS로 짰다.

 

이 문제를 풀기 위해서 check 리스트만 잘 만들어 주면 쉽게 풀 수 있는 문제였던 것 같다.

 

check리스트의 크기는 입력값과 똑같이 만들어 주면 된다. 값들은 전부 0으로 초기화 해줬다.

 

중첩 for문으로 입력된 정사각형 모양의 리스트를 하나하나 탐색하는데, 이때 입력받은 리스트(입력 값)의 값이 1이고, check리스트의 값이 0 (방문한 적 없음)일 때 dfs함수를 실행해 줬다.

 

dfs함수에서는 상하좌우 탐색을 하며 1을 찾을 때마다 카운트해줬다. 그리고 모든 상하좌우 탐색이 끝났을 때 카운트 한 값을 return으로 넘겨주고 정답 리스트에 append 해줬다.

 

출력할 때는 정답리스트를 오름차순으로 정렬하고, 정답리스트의 길이(len)를 출력 후, 모든 정답리스트의 값을 출력해 주면 된다!

 

정답

import sys

def dfs(c, r) :
    global count
    if c < 0 or c >= num or r < 0 or r >= num :
        return
    if arr[c][r] == '1' and check_arr[c][r] == 0:
        count += 1
        check_arr[c][r] = 1
        for k in range(4) :
            dfs(c+dx[k], r+dy[k])
        return count
    


num = int(input())
check_arr = [[0 for _ in range(num)] for _ in range(num)]
arr = []
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
for i in range(num) :
    arr.append(input())

ans = []

for i in range(0, num) :
    for j in range(0, num) :
        if check_arr[i][j] == 0 and arr[i][j] == '1':
            count = 0
            ans.append(dfs(i, j))
print(len(ans))
ans.sort()
for n in ans :
    print(n)