[코딩테스트] 백준 2667번: 단지번호붙이기

1. 아이디어

▪ 2중 for문 돌면서 1이고 방문하지 않았으면 dfs

   - 집의 수 변수 0으로 초기화

   - 방문여부 갱신

   - 단지수 += 1

   - 집의 수 결과 리스트에 append

▪ dfs

   - 재귀함수로 구현

   - 처음 호출 부분에 집의 수 += 1

      - 이때 호출받은 집의 수는 global로 구현

   - 입력받은 좌표의 상하좌우 재귀호출

   - 이때 상하좌우 자표가 지도의 크기를 넘지 않는 지 확인

      - 1이고 방문하지 않았으면

        - 방문여부 갱신

        - dfs 함수로 재귀호출

2. 시간복잡도

▪ O(V+E) = O(V+4V) = O(5V) = 5*25*25

3. 변수

▪ map: int[][]

▪ 방문여부: int[][]

▪ 단지수: int

▪ 집의 수 결과 리스트: int[]

4. 오답노트 

▪ dfs 함수 재귀호출 하기 전에 방문여부 갱신하기

code

import sys

input = sys.stdin.readline

N = int(input())
map = [list(map(int,input().strip())) for _ in range(N)]
chk = [[False]*N for _ in range(N)]
cnt = 0
rs = []

def dfs(j,i):
    my = [1,0,0,-1]
    mx = [0,1,-1,0]

    global each_cnt
    each_cnt +=1

    for k in range(4):
        ny, nx = j + my[k], i + mx[k]
        if 0 <= ny < N and 0 <= nx < N:
            if map[ny][nx] == 1 and chk[ny][nx] == False:
                chk[ny][nx] = True # 오답노트
                dfs(ny,nx)

for j in range(N):
    for i in range(N):
        if map[j][i] == 1 and chk[j][i] == False:
            cnt += 1
            chk[j][i] = True
            each_cnt = 0
            dfs(j,i)
            rs.append(each_cnt)

print(cnt)
rs.sort()
for x in rs:
    print(x)

 

2667번: 단지번호붙이기