Algorithm) DFS/BFS 실전문제

🍺 1번 음료수 얼려먹기

 

N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 

구멍이 뚫려있는 부분끼리 상,하,좌,우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 

이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성

==> DFS로 해결 ! 얼음을 얼릴 수 있는 공간이 상하좌우로 연결되어있다고 표현할 수 있으므로 그래프 형태로 모델링 가능 ! 

1) 특정한 지점의 주변 상하좌우를 살펴본 뒤에 주변 지점 중에서 값이 0 이면서 아직 방문하지 않은 지점이 있다면 해당 지점 방문

2) 방문한 지점에서 다시 상하좌우를 살펴보면서 방문을 다시 진행하며, 연결된 모든 지점 방문 가능 

3) 1-2번의 과정을 모든 노드에 반복하여 방문하지 않은 지점의 수를 센다 ! 

 

#N,M을 공백으로 구분하여 입력받기
n, m = map(int, input())

# 2차원 리스트의 맵 정보 입력받기
graph = []
for i in range(n):
    graph.append(list(map(int, input())))
    
# DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문 ! 
def dfs(x, y):
    #주어진 범위를 벗어나는 경우에는 즉시 종료 
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return false 
    # 현재 노드를 아직 방문하지 않았다면 
    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

# 모든 노드에 대하여 음료수 채우기 
result = 0
for i in range(n):
    for j in range(m):
        # 현재 위치에서 DFS 수행 
        if dfs(i, j) == True:
            result += 1
        
print(result)

DFS 를 사용해서 구분된 공간을 전부 방문한다 ! - 이어져 있는 곳의 탐색이 끝났을 경우 true를 반환하여 1개의 영역이 세어지게 된다 !

모든 노드들에 대해서 수행한다 ! 

 

 

👀 2번 미로 탈출 

 

동빈이는 N x M 크기의 직사각형 형태의 미로에 갇혀있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야한다.

동빈이의 위치는 (1,1) 이고 미로의 출구는 (N, M)의 위치에 존재하며 한번에 한 칸씩 이동 할 수 있다. 

이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다.

미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수. 

마지막 칸과 시작칸을 모두 포함하여 계산 

==> BFS 로 해결 ! BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색한다 !

그러므로 1,1 에서 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣자 ! 특정 노드에 방문하면 그 이전 노드의 거리에 1을 더한 값을 리스트에 넣는다. 참고로, 본 문제에서는 단순히 가장 오른쪽 아래 위치로 이동하는 것을 요구하기 때문에 다시 돌아갈 경우 돌아간 곳의 위치값이 증가하는 경우는 없다 ! 

 

from collections import deque

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

# 이동할 네 방향 정의 - 상하좌우
dx = [-1,1,0,0]
dy = [0,0,-1,1]

# BFS 소스코드 구현
def bfs(x, y):
    # 큐 구현을 위해 deque 라이브러리 사용
    queue = deque()
    queue.append((x,y))
    # 큐가 빌때까지 반복
    while queue:
        x, y = queue.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
                queue.append((nx, ny))
    # 가장 오른쪽 아래까지의 최단 거리 반환 
    return graph[n-1][m-1]

# 결과 출력
print(bfs(0,0))