백준[2667] - 단지번호붙이기

 

 

문제

2667번: 단지번호붙이기

 

 

 

작성한 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N = int(input())
graph = [list(map(int, input().rstrip())) for _ in range(N)]

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

cnt = 0
result = list()

def dfs(x, y):
    global cnt
    if x < 0 or x >= N or y < 0 or y >= N:
        return False

    if graph[x][y] == 1:
        cnt += 1
        graph[x][y] = 0
        for i in range(4):
            dfs(x+dx[i], y+dy[i])
        return True

for i in range(N):
    for j in range(N):
        if dfs(i, j) == True:
            result.append(cnt)
            cnt = 0
            
result.sort()
print(len(result))
for i in result:
    print(i)

- DFS, BFS 두 가지 방법 모두 사용해서 문제를 풀 수 있다. (나는 DFS로 풀어보았다. → 재귀함수 사용)

 

- N : (NxN) 지도 크기

- graph : N번 for문 돌리되, 한 줄씩 입력받는 내용은 각각 int형으로 형변환해서 list로 저장 (리스트 안에 리스트) → 1은 집O / 0은 집X

 

- 시작점이 정해져 있지X 떄문에 → 전체적으로 탐색해야 하며, 그러기 위해서는 방향벡터가 필요하다.

   : 각 인덱스를 [상,하,좌,우] 라고 생각했을 때 → dx(x의 변화량) = [0, 0, -1, 1] / dy(y의 변화량) = [-1, 1, 0, 0]

- cnt : 단지 내 집의 개수

- result : 집의 개수 정보를 담을 리스트

 

- 만약 x, y 좌표 각각 0보다 작거나 N보다 크거나 같은 경우 → (NxN)보다 작거나 크다는 소리이기 때문에 성립X → False 반환

- graph[x][y] 값이 1일 경우 (집이 있을 경우) → True 반환

   : cnt의 값을 1 증가시킨다.

   : graph[x][y] = 0 → 탐색중인 위치를 0으로 바꿔 다시 방문하지 않도록 한다.

   : 상하좌우(range(4)) 각 방향 별로 돌면서(x+dx[i] / y+dy[i]) 위의 로직을 다시 확인한다. (재귀함수)

 

- (NxN) 전체적으로 확인하기 위해 이중 for문을 돌린다.

   : dfs(i, j)의 반환값이 True일 경우 → result에 cnt 값을 추가하고, cnt를 0으로 초기화 시킨다.

 

- result 내부 요소들을 오름차순으로 출력하기 위해서 sort()를 통해 오름차순으로 정렬해준다.

- 처음 출력해야 할 사항이 단지의 개수이기 때문에 → len(result)를 출력하고, for문을 돌면서 result 내부 요소를 한 줄씩 출력해준다.