[백준]1261 알고스팟 - 골드 4

[오늘의 문제]

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

---

[오늘의 학습 키워드]

• 다익스트라, 0-1BFS, 구현

---

1. 문제설명

 

쉽게 말해 0, 0 위치에서 미로의 끝 M, N 으로 이동하려고 하는데 

벽을 최소한으로 부수면서 이동하는 경우를 찾는 문제입니다.

---

[제한사항]

• 시간 제한 1초
• 메모리 제한 128MB
• 1 ≤ N, M ≤ 100
• 시작위치와 종료위치는 항상 뚫려있다.

---

2. 접근방식

 

문제를 보자마자 이건 다익스트라? 보다는 BFS 문제 같은데 라고 생각했습니다.

 

입력에 배열이 주어지고 배열을 탐색하여 목적지까지 이동하는 것이 기존의 BFS 코드와 다를게 없었기 때문입니다.

 

그러나 문제는 벽이 있는 경우와 없는 경우 였습니다.

 

목적지까지 도착할 때 벽을 최소한으로 부수고 이동해야하니 기존의 BFS 탐색을 그대로 하면 결과가 틀리게 출력될 것입니다.

 

그럼 queue에 우선순위를 부여하면 되지 않을까 싶어서 appendLeft를 사용해보기로 했습니다.

 

벽이 없는 경우를 우선적으로 탐색하기 위해 미로를 탐색하며 벽이 없는 경우 queue의 왼쪽에 삽입해 줍니다.

 

또 벽이 있는 경우 queue의 오른쪽에 삽입하여 벽이 없는 경우를 우선적으로 모두 탐색하고, 그 다음 벽이 있는 경우를 탐색하도록 설정하였습니다.

 

이렇게 문제를 해결하고보니 이 코드가 0-1 BFS 알고리즘 해결에 사용되는 코드란것을 알게 되었습니다.

---

3. 코드

import sys
input = sys.stdin.readline
from collections import deque

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

# 0 - 1 BFS
def BFS(x, y):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = 0

    # 기존의 BFS 동작과 동일
    while queue:
        x, y = queue.popleft()

        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]

            # 미로의 범위 안, 미방문 지역인 곳을 탐색하는데
            if 0 <= nx < M and 0 <= ny < N and visited[nx][ny] == -1:
                
                # 벽이 없는 경우 우선 탐색을 위해 appendLeft 사용
                if maze[nx][ny] == 0:
                    visited[nx][ny] = visited[x][y]
                    queue.appendleft((nx, ny))
                
                # 벽이 있는 곳은 append로 queue에 넣어주며 벽을 부순 횟수 증가시켜주기
                else:
                    visited[nx][ny] = visited[x][y] + 1
                    queue.append((nx, ny))

# 입력
N, M = map(int, input().split())
maze = [list(map(int, input().strip())) for _ in range(M)]
visited = [[-1] * N for _ in range(M)]
BFS(0, 0)
print(visited[M-1][N-1])

---

[코드설명]

# 기존의 BFS 동작과 동일
    while queue:
        x, y = queue.popleft()

        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]

            # 미로의 범위 안, 미방문 지역인 곳을 탐색하는데
            if 0 <= nx < M and 0 <= ny < N and visited[nx][ny] == -1:
                
                # 벽이 없는 경우 우선 탐색을 위해 appendLeft 사용
                if maze[nx][ny] == 0:
                    visited[nx][ny] = visited[x][y]
                    queue.appendleft((nx, ny))
                
                # 벽이 있는 곳은 append로 queue에 넣어주며 벽을 부순 횟수 증가시켜주기
                else:
                    visited[nx][ny] = visited[x][y] + 1
                    queue.append((nx, ny))

 

기존의 BFS 동작과 동일한데 핵심 로직은 이부분 입니다.

 

BFS 탐색을 실시하며, 미방문 지역을 방문 처리할건데 벽이 없는 경우를 우선적으로 탐색하기 위해

벽이 없으면 appendLeft로 왼쪽에 삽입해주었고

 

벽이 있으면 append로 오른쪽에 삽입해 주었습니다.

 

그 외 동작은 기존의 BFS와 동일합니다.

---

4. 결과

---

[회고]

 

기존의 BFS를 전부 구현한 상태에서 예제2번이 제대로 출력이 안되니 이걸 어떻게 구분하지 고민을 조금 오래했습니다.

 

다양한 아이디어가 떠올랐는데 DFS 탐색을 통해 백트래킹을 실시하여 모든 경우의 수를 구하고 그 때마다 최소의 값으로 초기화 하는 방법을 생각했는데

 

최대 100 * 100 이라 모든 칸을 중복없이 한 번씩 방문한다고 해도 100! 이 나오니 안될것 같았습니다.

벽이 있는 경우와 없는 경우를 구분해도 없는 경로를 탐색하다 막히면 결국 벽을 뚫고 이동해야 하니 아닌것 같았습니다.

 

그러다 결국 경우의 수는 벽을 뚫고 가는 경우, 벽을 뚫지 않고 가는 경우 2가지 뿐이니까 우선적으로 벽을 안뚫고 최대한 이동하다가 안되면 벽을 뚫으면 되지 않을까? 라고 생각했고

 

그럼 벽이 없는 곳 먼저 찾자는 생각에 appendLeft가 생각났습니다.

 

나중에 찾아보니 appendLeft 와 append로 큐의 삽입을 다르게 하여 조건을 분기하는 것을 0-1BFS 라고 하였습니다.

 

나중에 다익스트라 코드도 찾아보니 BFS와 크게 다르지 않았고 결론적으로는 BFS로 문제를 해결할 수 있었습니다.