백준 2667 단지번호붙이기 (DFS, 그래프 탐색)

이번 문제는 생각보다 쉽게 풀렸다. DFS의 기본 코딩 구조를 알면 바로 대입이 가능한 문제였다.

문제는 1이 집들이고 붙어 있는 집끼리 단지를 조성한다. 그리고 단지의 개수를 확인하고 단지별 개수를 오름차순으로 출력하는 문제이다.

이 문제를 풀기 위해서는 뇌피셜로 필요하다고 생각되는 요소를 정리해 보았다.

1. DFS를 스택을 활용하여 코딩을 구현할 수 있는지

2. DFS로 행렬들의 인접을 어떻게 파악할건지

3. 다음 단지는 어떻게 찾을건지

 

우선 DFS를 스택을 활용하여 코딩하는건 넘어간다. 

그럼 2번 DFS로 행렬들의 인접을 어떻게 파악할건지 생각해본다. 현재 (0,1)에서 가장 먼저 집이 발견된다. 문제는 동서남북 모두 확인하여 인접한 행렬을 확인해야 하는데 위에는 접근할 수가 없다.

따라서 <그림 1> 에 패딩을 추가해 준다.

 

다음과 같이 패딩을 0으로 입력해주면 쉽게 오고 갈 수 있다.

 

 

 

 

 

이제는 3번 다음 단지를 어떻게 접근할 건지 생각해본다. 그러다 생각이 든건 이중포문으로 행렬에 하나하나씩 접근하되 단지를 구하는 로직에서 들른 집들은 0처리를 해준다. 그러면 단지화 된 건물들은 행렬에 뜨지 않기 때문에 다음 단지에 접근하기가 수월해 진다.

즉, 1번단지를 구할때 들른 집들은 0으로 값을 바꾸어 준다는 소리다.

이러한 몇가지 요소를 코드로 구현하면 아래와 같다.

n = int(input())
L=[]
for i in range(n):
    line = list(map(int, list(input())))
    L.append([0]+line+[0])
L = [[0 for i in range(n+2)]] + L + [[0 for i in range(n+2)]]

def DFS(i, j):
    stack = [(i,j)]
    out = []
    while stack:
        t = stack.pop()
        a,b = t
        if t not in out:
            out.append(t)
            L[a][b] = 0 # 지워버려
            #위쪽 오른쪽 위 아래
            tmp = []
            if L[a][b-1] == 1:
                tmp += [(a,b-1)] 
            if L[a][b+1] == 1:
                tmp += [(a,b+1)]
            if L[a+1][b] == 1:
                tmp += [(a+1, b)]
            if L[a-1][b] == 1:
                tmp += [(a-1,b)]
            tmp = list(set(tmp) - set(out))
            stack += tmp
    return len(out)

num = []
for i in range(n):
    for j in range(n):
        if L[i+1][j+1] == 1:# DFS시작!
            num.append(DFS(i+1,j+1))
print(len(num))
num.sort()
for i in num:
    print(i)

실버 1이었는데 생각보다 빨리 풀렸다. 기분이 나이스 하다~

아마 BFS로 풀어도 똑같이 풀렸을것이라 예상된다.

 

이번에는 스터디 때문에 다시 풀어보았다. 이번에는 패딩없이 인덱스 단위에서 접근가능한지 확인하고 BFS를 해보았다. 중간중간 큐에 또 들어가지 말라고 확인해 주는 작업을 해서 그런지 이전보다는 시간이 좀 더 걸렸다.

from collections import deque

n = int(input())
m =[]
for i in range(n):
    m.append(list(map(int, input())))

def bfs(i,j):
    dx=[0,0,1,-1]#동서남북
    dy=[1,-1,0,0]
    queue = deque([[i,j]])
    count = 0

    while len(queue) != 0:
        x,y = queue.popleft()
        count += 1
        m[x][y] = 0
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx and nx<n and 0<=ny and n>ny:
                if (m[nx][ny] == 1) and ([nx,ny] not in queue):
                    queue.append([nx,ny])
    return count
total = []
for i in range(n):
    for j in range(n):
        if m[i][j] == 1:
            total.append(bfs(i,j))

print(len(total))
total.sort()
for i in total:
    print(i)