[BOJ] 2667번 단지번호 붙이기 / 사용언어 : 파이썬(python)

※ 문제링크

2667번: 단지번호붙이기

해당문제는 DFS와 BFS를 활용하여 풀 수 있는 문제였다. 조건은 간단하여 풀이방법을 떠올리는 것은 그리 어렵지 않았으나, 구현하는난이도가 생각보다 어려워서 꽤나 시간이 걸린 문제였다. 풀이방법에 대해 간단하게 이야기하면, 입력받은 문자열을 2차원 배열로 변환한 후, 배열 상 값이 1인 경우에 한하여 DFS 또는 BFS를 활용하여 해당 점을 기준으로 상, 하, 좌, 우를 확인하여 조건 충족하면 계속 탐색하여 결과를 작성하는 방식으로 해결하였다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 N값과 문자열을 바탕으로 2차원 배열로 변환하여 준다.

2. DFS의 경우 재귀를 활용하여, BFS의 경우 파이썬 내장함수의 deque를 활용하여 함수를 작성해준다.

3. 2중 반복문을 활용하여 2차원 배열의 처음부터 끝까지 탐색해주고, 탐색 후 결과값을 출력해준다.

+ 연산시간 최소화를 위해 sys함수를 활용하였으며, 해당 함수 활용시에는 개행문자를 유의하여 작성해주었다.

 

# DFS 풀이
import sys
N = int(input())
apt = []
for _ in range(N): 
    sp = input()
    apt_d = []
    for num in sp:
        apt_d.append(int(num))
    apt.append(apt_d)

def dfs(x, y, apt_n):
    visited[x][y] = True
    global nums
    if apt[x][y] == 1:
        apt[x][y] = apt_n
        nums += 1
    
    for t in range(4):
        nx = x + dx[t]
        ny = y + dy[t]
        if 0 <= nx < N and 0 <= ny < N:
            if apt[nx][ny] == 1 and visited[nx][ny] == False:
                dfs(nx, ny, apt_n)

visited = [[False] * N for _ in range(N)]
# apt_dic = dict()
house_num = []
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
apt_n = 1
nums = 0
for i in range(N):
    for k in range(N):
        if apt[i][k] == 1 and visited[i][k] == False:
            dfs(i, k, apt_n)
            # apt_dic[apt_n] = nums
            house_num.append(nums)
            nums = 0
            apt_n += 1
house_num.sort()
sys.stdout.write(f'{len(house_num)}\n')
for i in range(len(house_num)):
    if i == len(house_num) - 1:
        sys.stdout.write(f'{house_num[i]}')
    else:
        sys.stdout.write(f'{house_num[i]}\n')
        
# BFS 풀이
from collections import deque
import sys

N = int(input())
apt = []
for _ in range(N): 
    sp = input()
    apt_d = []
    for num in sp:
        apt_d.append(int(num))
    apt.append(apt_d)

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

def bfs(apt, x, y, apt_n):
    queue = deque()
    queue.append([x,y])
    while True:
        if apt_n not in apt_name:
            apt_name.append(apt_n)
            apt[x][y] = apt_n
            break
        else:
            apt_n -= 1
    count = 1

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if apt[nx][ny] == 1:
                    apt[nx][ny] = apt_n
                    queue.append([nx, ny])
                    count += 1
    return count

house_num = []
for i in range(N):
    for k in range(N):
        if apt[i][k] == 1:
            house_num.append(bfs(apt, i, k, apt_n))

house_num.sort()
sys.stdout.write(f'{len(house_num)}\n')
for i in range(len(house_num)):
    if i == len(house_num) - 1:
        sys.stdout.write(f'{house_num[i]}')
    else:
        sys.stdout.write(f'{house_num[i]}\n')

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.