[알고리즘] 소프티어 Lv2. 장애물 인식 프로그램 (백준 2667번 단지번호 붙이기) (Python, DFS, BFS)

Softeer 알고리즘 문제 풀이

문제: Lv2. 장애물 인식 프로그램

 

https://softeer.ai/practice/6282

Softeer - 현대자동차그룹 SW인재확보플랫폼

문제가 뭔가 많이 익숙하다,, 하고 백준에서 풀어봤던 문제를 찾아봤는데, 똑같은 문제를 발견했다.

https://www.acmicpc.net/problem/2667

(심지어 Java 풀이 정리도 해놓음)

2022.04.24 - [알고리즘/백준 문제 풀이] - [백준 JAVA 문제풀이] 알고리즘(너비 우선 탐색)- 2667번 단지번호 붙이기

어쨌거나,, 너무 오랜만에 풀어봐서 dfs, bfs 다 까먹었기에 다시 공부하면서 풀었다.

 

DFS 풀이

import sys

input = sys.stdin.readline

n = int(input())  # 지도 크기

mymap = [list(map(int, input().rstrip())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]  # 방문 여부

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

def dfs(r, c, cnt):
    visited[r][c] = True  # 방문 처리
    cnt += 1  # 현재 집 포함

    for i in range(4):
        ny = r + dy[i]
        nx = c + dx[i]

        if 0 <= ny < n and 0 <= nx < n and not visited[ny][nx] and mymap[ny][nx] == 1:
            cnt = dfs(ny, nx, cnt)  # 재귀적으로 연결된 블럭 탐색

    return cnt  # 단지 크기 반환

cnt_list = []
for i in range(n):
    for j in range(n):
        if mymap[i][j] == 1 and not visited[i][j]:
            cnt_list.append(dfs(i, j, 0))

cnt_list.sort()  # 장애물 크기 오름차순 정렬

print(len(cnt_list))  # 장애물 개수 출력
for cnt in cnt_list:
    print(cnt)

🔹 코드 설명

1. DFS 탐색
   • 방문하지 않은 1을 발견하면 dfs() 호출.
   • dfs()는 연결된 모든 1을 탐색하면서 cnt 값을 증가.
   • cnt 값을 리턴하면서 단지의 크기를 기록.
2. 탐색 완료 후 정렬
   • 모든 단지를 찾은 후 cnt_list.sort()를 이용해 오름차순 정렬.
3. 결과 출력
   • 장애물 개수와 각 장애물의 크기를 출력.

 

BFS 풀이

BFS가 스택 오버플로우 위험이 적고, 재귀 없이 큐로 처리하므로 실전에서는 BFS가 더 안정적이라고 한다.
➡️ DFS보다 재귀 깊이 문제가 없어서 더 안정적

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())  # 지도 크기

mymap = [list(map(int, input().rstrip())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]  # 방문 여부

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


def bfs(r, c):
    queue = deque([(r, c)])
    visited[r][c] = True
    cnt = 1  # 시작 지점 포함

    while queue:
        y, x = queue.popleft()

        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if 0 <= ny < n and 0 <= nx < n and not visited[ny][nx] and mymap[ny][nx] == 1:
                queue.append((ny, nx))
                visited[ny][nx] = True
                cnt += 1

    return cnt

cnt_list = []
for i in range(n):
    for j in range(n):
        if mymap[i][j] == 1 and not visited[i][j]:
            cnt_list.append(bfs(i, j))

cnt_list.sort()  # 장애물 크기 오름차순 정렬

print(len(cnt_list))  # 장애물 개수 출력
for cnt in cnt_list:
    print(cnt)

📌  BFS 동작 방식

1. queue 에 시작 지점 (r, c) 추가하고 방문 처리
2. 큐가 빌 때까지 반복
   • 현재 위치 (y, x)를 꺼냄
   • 상하좌우 탐색:
     • 범위 내에 있고 (0 <= ny < n, 0 <= nx < n)
     • 아직 방문하지 않았으며 (not visited[ny][nx])
     • 집이 있는 경우 (mymap[ny][nx] == 1)
     • 큐에 추가하고 visited 처리
     • 단지 크기 (cnt) 증가
3. 모든 연결된 집 탐색 완료 후 cnt 반환