[코딩공부] DFS/BFS(3) - 문제 풀이

1. 음료수 얼려 먹기 

 

NXM 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상하좌우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오 다음의 4X5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다. 

 

예시 )

 

00110

00011

111111

00000  

 

풀이)

n, m = map(int,input().split())

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

def dfs(x,y):
    if x <= -1 and x >= n and y <= -1 and y >= m:
        return False
    if graph[x][y] == 0
        graph[x][y] = 1
        dfs(x-1,y)
        dfs(x+1,y)
        dfs(x,y+1)
        dfs(x,y-1)
        return True

result = 0
for i in range(n):
    for j in range(m):
        if dfs(i,j):
            result += 1

 

이 문제를 풀면서 상당히 오랜만에 문제를 풀어서 그런지 이해하는데 조금 시간이 걸렸습니다. 즉 graph에 0이 들어 있으면 그 주변 전체를 다 1로 바꾸고 result + 1을 해주는 쉬운 방식에도 불구하고 그랬습니다. 조금 창피하네요 앞으로는  시간이 없더라도 더 열심히 문제를 풀어야할 것 같습니다. 

 

2) 미로 탈출 

 

동빈이는 NXM 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 타출해야 한다. 동빈이의 위치는 (1,1) 이고 미로의 출구는 (N,M)의 위치하고 존재하며 한번에 한 칸씩 이동할 수 있다. 이 때 괴물이 있는 부분은 0으로 괴물이 없는 부분은 1로 표시되어 있다. 이 때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀때는 시작 칸과 마지막 칸을 모두 계산 포함해서 계산한다.  

 

어떻게 보면  가장 흔한 형태의 문제이고 이 문제에서도 BFS를 활용하면 간단하게 해결할 수 있다고 언급하고 있습니다. 

from collections import deque

# 1) 입력 받기
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

# 2) 이동 방향 (상하좌우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs():
    q = deque()
    q.append((0, 0))
    visited = [[False]*m for _ in range(n)]
    visited[0][0] = True
    
    # distance[x][y] = (0,0)에서 (x,y)까지 최단 거리
    distance = [[0]*m for _ in range(n)]
    distance[0][0] = 1  # 시작점 포함 카운트

    while q:
        x, y = q.popleft()
        # 도착지에 다다랐으면 바로 반환해도 무방
        if x == n-1 and y == m-1:
            return distance[x][y]
        
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            # 3) 경계 검사: 0 ≤ nx < n, 0 ≤ ny < m
            if not (0 <= nx < n and 0 <= ny < m):
                continue
            # 4) 벽(0)이거나 이미 방문한 칸이면 skip
            if graph[nx][ny] == 0 or visited[nx][ny]:
                continue
            
            visited[nx][ny] = True
            distance[nx][ny] = distance[x][y] + 1
            q.append((nx, ny))
    
    # 도달 불가한 경우
    return -1

print(bfs())