[BOJ 2667] 단지번호붙이기

문제 요약

문제 요약
정사각형 모양의 지도에 집들의 배치가 있다.
좌우, 위아래로 연결된 집의 모임을 단지라고 한다.
단지가 몇개인지 출력하고, 각 단지의 집의 수를 오름차순으로 정렬하여 출력하라
입력
지도의 크기 N
그 다음 N줄에 지도의 자료(0or1)이 입력
출력
총 단지수 출력
각 단지내 집의 수를 오름차순으로 정렬

풀이

DFS, BFS중에서 DFS를 선택하여 아래와 같은 순서로 문제를 풀었다.

1. 입력 받은 것을 배열에 집어넣는다
2. 전수조사하면서 DFS를 한다
   -> DFS하는 동안 visited에 단지번호를 저장한다.
   -> 새로 DFS를 하면 단지번호를 +1 한다.
3. visited를 조사해서 출력한다.

입력받은 것을 어떻게 배열에 넣을까?

이런식으로 띄어쓰기가 없는 형식은 어떻게 list에 저장할 수 있을까?
map을 통해 input 받은 것을 int로 변환한 뒤 list에 저장한다.
단 \n은 int로 변환하지 못하기에 rstrip으로 잘라내야한다.

L = []; visited = [[0 for _ in range(N)] for _ in range(N)]
for _ in range(N):
    L.append(list(map(int, input().rstrip())))

DFS는 어떻게 해야할까?

def DFS(x, y, cnt):
    # right
    if  x+1 != N and L[y][x+1] == 1 and visited[y][x+1] == 0:
        visited[y][x+1] = cnt
        DFS(x+1,y,cnt)
    # down
    if y+1 != N and L[y+1][x] == 1 and visited[y+1][x] == 0:
        visited[y+1][x] = cnt
        DFS(x,y+1,cnt)
    # left
    if x-1 != -1 and L[y][x-1] == 1 and visited[y][x-1] == 0:
        visited[y][x-1] = cnt
        DFS(x-1,y,cnt)
    # up
    if y-1 != -1 and L[y-1][x] == 1 and visited[y-1][x] == 0:
        visited[y-1][x] = cnt
        DFS(x,y-1,cnt)

기본적으로 2차원 배열을 탐색하므로 x, y값을 파라미터로 설정하고 cnt를 통해 단지수를 visited 배열에 기록하도록 하여 DFS 코드를 짠다.
4방향을 탐색할 때는 다음 조건을 검사한다.

• 배열의 끝부분인가?
• 집이 있는 곳인가?
• 방문하지 않은 곳인가?

아쉬운 점

for문과 if문이 여러번 곂치다보니 코드가 지저분해보이는 점이 조금 아쉽다.
그리고 변수를 잘 쓰면 DFS로 처리하는 과정에서 for문을 한 개로 줄일 수 있을 것 같다.

결과 코드

import sys
input = sys.stdin.readline

N = int(input())

L = []; visited = [[0 for _ in range(N)] for _ in range(N)]
for _ in range(N):
    L.append(list(map(int, input().rstrip())))

def DFS(x, y, cnt):
    # right
    if  x+1 != N and L[y][x+1] == 1 and visited[y][x+1] == 0:
        visited[y][x+1] = cnt
        DFS(x+1,y,cnt)
    # down
    if y+1 != N and L[y+1][x] == 1 and visited[y+1][x] == 0:
        visited[y+1][x] = cnt
        DFS(x,y+1,cnt)
    # left
    if x-1 != -1 and L[y][x-1] == 1 and visited[y][x-1] == 0:
        visited[y][x-1] = cnt
        DFS(x-1,y,cnt)
    # up
    if y-1 != -1 and L[y-1][x] == 1 and visited[y-1][x] == 0:
        visited[y-1][x] = cnt
        DFS(x,y-1,cnt)

cnt = 0
for y in range(N):
    for x in range(N):
        if L[y][x] == 1 and visited[y][x] == 0:
            cnt += 1
            visited[y][x] = cnt
            DFS(x,y,cnt)

res = [0 for _ in range(cnt)]
for y in range(N):
    for x in range(N):
        if visited[y][x] != 0:
            res[visited[y][x]-1] += 1

print(cnt, end='')
for r in sorted(res):
    print()
    print(r, end='')