2667번 - 단지번호붙이기(python3)

문제 링크 : https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

출처 : 백준 문제

<그림 1>과 같이 지도가 주어집니다. 0은 빈 곳, 1은 집이 있는 곳이고, 집이 상하좌우로 붙어있는 경우에는 그 집들을 하나의 단지로 생각합니다. 대각선으로 있는 경우는 같은 단지라고 생각하지 않습니다. 몇 개의 단지가 있는지, 각 단지에 집이 몇 개 있는지 오름차순으로 출력하면 됩니다. 위 그림의 경우는 순서대로 3 7 8 9를 출력하면 됩니다.

 

DPS 또는 BFS를 사용해서 풀 수 있고, 저는 stack을 이용해 DFS로 풀었습니다.

import sys

def dfs(x, y):
    if x < 0 or x >= n or y < 0 or y >= n or lst[x][y] == '0':
        return 0#시작점이 0이면 바로 종료
    
    #지점에 아파트가 있는 경우
    stack = []
    lst[x][y] = '0' #이미 지나온 곳 0으로 초기화
    count = 1
    stack.append([x,y])
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    while stack: #스택이 차 있는 동안
        loc = stack.pop()
        for i in range(4):
            new_x = loc[0]+dx[i]
            new_y = loc[1]+dy[i]
            if 0 <= new_x < n and 0 <= new_y < n and lst[new_x][new_y] == '1':
                stack.append([new_x, new_y]) #스택에 집 추가
                count += 1 #집 개수 + 1
                lst[new_x][new_y] = '0' #이미 지나온 곳 0으로 초기화

    return count

n = int(sys.stdin.readline())
lst = [list(sys.stdin.readline()) for _ in range(n)]
sol = []

for r in range(n):
    for c in range(n):
        num_apt = dfs(r, c) #모든 지점에 대해 수행
        if num_apt:
            sol.append(num_apt)

sol.sort()
print(len(sol))
for j in range(len(sol)):
    print(sol[j])

현재 위치가 0이면 바로 return하고, 1이면 stack에 집어넣고 탐색을 시작합니다. 한 번 탐색한 집은 재탐색을 막기 위해 0으로 바꿔주고, 단지 내 집 개수를 알아야 하기 때문에 count라는 변수를 이용합니다. 한 단지의 탐색이 모두 끝나면 count를 return해서 sol이라는 list에 따로 모아둡니다. 마지막에 오름차순으로 출력해야 하기 때문에 sol.sort()를 하고 출력합니다.(이거 빼먹고 10분 정도 왜 틀렸지 고민했습니다...)

 

DFS, BFS를 학부 알고리즘 수업때만 배우고 과제해서 내고 직접 코테 연습문제를 응용해서 풀어본 건 처음 같습니다. 역시 수업 듣고 끝! 이게 아니라 응용해서 풀 수 있는 능력이 필요합니다.. 비슷한 유사 문제가 매우 많은데, 당분간은 이런 문제 꾸준히 풀어서 감을 익혀야 할 것 같습니다.