[코딩테스트]Chapter 5. DFS/BFS - 실전문제

실전문제 3. 음료수 얼려 먹기 (DFS)

N X M 얼음 틀에서 생성되는 총 아이스크림의 개수 구하기

0이 모여있는 묶음이 몇 개 인지 묻는 문제

# 얼음틀 크기
n, m = map(int, input().split())

# 2차원 그래프 입력
graph = [list(map(int, input())) for _ in range(n)]

def dfs(x, y):
	# 얼음틀 범위를 벗어나는 경우
    if x < 0 or x >= n or y < 0 or y >= m:
        return False
    # 0이 얼음을 얼릴 수 있는 부분
    if graph[x][y] == 0:
    	# 방문 처리
        graph[x][y] = 1
        # 사방에 연결된 칸에 대해 재귀호출
        dfs(x-1, y)
        dfs(x, y-1)
        dfs(x+1, y)
        dfs(x, y+1)
        return True
    return False

answer = 0
for i in range(n):
    for j in range(m):
    	# 모든 칸에 대해 dfs 탐색, 결과가 True면 한 묶음
        if dfs(i, j):
            answer += 1

print(answer)

유사한 문제

Softeer 장애물 인식 프로그램

문제

n = int(input())

graph = [list(map(int, input())) for _ in range(n)]

def dfs(x, y):
    if x < 0 or x >= n or y < 0 or y >= n:
        return 0
    if graph[x][y]:
        graph[x][y] = 0
        
        count = 1     # 크기 측정을 위해
        count += dfs(x-1, y)
        count += dfs(x, y-1)
        count += dfs(x+1, y)
        count += dfs(x, y+1)
        return count
    return 0

answer = []
for i in range(n):
    for j in range(n):
        res = dfs(i, j)
        if res:
            answer.append(res)

print(len(answer))
answer.sort()
for a in answer:
    print(a)

단순 묶음 개수만 체크하는 것이 아니라 각 묶음의 크기도 측정해야하는 문제!

---

실전문제 4. 미로 탈출 (BFS)

N X M 미로에서 괴물을 피해 길 찾기

시작점에서 가까운 노드부터 탐색해 1을 따라 최소 이동 체크

from collections import deque

n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]

# 이동 정의
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y):
    q = deque()
    q.append((x, y))  # 큐에 시작점 삽입
    while q:
        x, y = q.popleft()
        for i in range(4):
            # 사방 연결 확인
            nx = x + dx[i]
            ny = y + dy[i]
            # 미로 크기를 벗어나는 경우
            if nx < 0 or ny < 0 or nx >= n or ny >= m:  
                continue
            # 벽을 만난 경우
            if graph[nx][ny] == 0:  
                continue
            # 해당 노드를 처음 방문하는 경우
            if graph[nx][ny] == 1:  
                graph[nx][ny] = graph[x][y] + 1 # 경로 기록
                q.append((nx, ny))  # 탐색을 위해 큐에 추가
    return graph[n-1][m-1]

print(bfs(0, 0))