99클럽 코테 스터디 15일차 TIL : 단지번호붙이기

 

 

화 / 목은 아무래도 늘어지는 날인거 같다 >.<

 

오늘의 코딩테스트 : 단지 번호 붙이기

 

map 이 등장하고 그래프 갯수를 세며 하나의 그래프 내에 들어있는 노드의 수를 계산하는 전형적인 DFS 문제이다.

DFS, 재귀함수의 경우 메모리 관리를 제대로하지 않으면 C 같은 경우 stack에 함수에 대한 정보 및 지역변수가 계속 쌓여서 stack overflow를 발생시키기도 한다.

 

 

 

늘 하는대로 DFS는 

1. dy, dx 설정해서 map 탐색하기

2. 최단거리를 구할 때는 map 정보를 바꿔서 가장 마지막에 누적해서 적기도하지만 오늘은 그래프 내의 노드의 갯수 즉, 재귀가 얼마나 발생했는지를 계산해야 하므로 cnt에 이전의 dfs에서 return한 값을 누적하도록 계산한다.

3. 출력 방식을 고려하여 반드시 sort가 필요하다.

 

import sys

sys.stdin = open("input.txt", "r")

N = int(input())

isVisited = [[0 for col in range(N)] for row in range(N)]
mapp = []

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

for i in range(N):
    arr = list(input())
    mapp.append(list(map(int, arr)))

answer = []

def dfs(y, x):
    # 처음 재귀의 시작
    cnt = 1
    isVisited[y][x] = 1
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]

        if ny < 0 or ny >= N or nx < 0 or nx >= N:
            continue
        else:
            if mapp[ny][nx] == 1 and isVisited[ny][nx] == 0:
                # 재귀 return으로 종료될 때 까지 계속 누적해주기
                cnt += dfs(ny, nx)
    #print("y : ", y, " x : ", x, "cnt : ", cnt)
    return cnt

for i in range(N):
    for j in range(N):
        if mapp[i][j] == 1 and isVisited[i][j] == 0:
            cnt = dfs(i,j)
            if cnt != 1:
                answer.append(cnt)

# 오름차순 정렬이라고 했으므로 잊지말고 정렬 후 출력하기!!
answer.sort()
print(len(answer))
for i in range(len(answer)):
    print(answer[i])