[백준] 2206 벽 부수고 이동하기

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

시작 좌표에서 도착 좌표까지 이동 시 최소 거리를 구할 필요가 있으므로 BFS 알고리즘을 이용하였습니다.

그리고 최대 한번 벽을 부수고 이동이 가능하므로 현재 이동에서 벽을 부수고 이동이 가능한지 여부도 계산이 필요했습니다.

 

기존의 BFS 이용 시 좌표별 거리 계산을 2차원 배열을 이용하였으나, 벽을 부수고 이동이 가능한지 여부를 기록하기 위하여 3차원 배열을 이용하였습니다.

크게 벽을 부수고 이동이 가능한 경우를 기록하는 2차원 배열과 벽을 부수지 않고 이동이 가능한 2차원 배열로 구분하였습니다.

 

다음 좌표의 벽 유무와 현재 조건에 따라 BFS 탐색을 하였고, 탐색이 모두 끝나면 두 2차원 배열에서 더 작은 값을 정답으로 출력하였습니다.

2) 알고리즘

• BFS

3) 풀이 코드

사용 언어 - Python

import sys
from collections import deque
sys.stdin = open('input.txt')


def solution():
    # 초기 시작 세팅
    q = deque([(1, 0, 0)])
    visited[1][0][0] = 1

    while q:
        remain, y, x = q.popleft()
        visit = visited[remain][y][x]

        # 상하좌우 이동
        for k in range(4):
            ny = y + dr[k]
            nx = x + dc[k]

            if 0 <= ny < N and 0 <= nx < M:
                # 다음 좌표가 벽이 아닌 경우
                if not board[ny][nx] and visited[remain][ny][nx] > visit + 1:
                    visited[remain][ny][nx] = visit + 1
                    q.append((remain, ny, nx))
                # 다음 좌표가 벽인 경우
                elif board[ny][nx] == 1 and remain and visited[remain-1][ny][nx] > visit + 1:
                    visited[remain-1][ny][nx] = visit + 1
                    q.append((remain-1, ny, nx))


# 위, 오른쪽, 아래, 왼쪽
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

# 입력 정보, 행과 열, 맵 정보
N, M = map(int, sys.stdin.readline().split())
board = [list(map(int, list(sys.stdin.readline().strip()))) for _ in range(N)]

# 맵 좌표별 이동 위한 최소 거리
# 2개의 2차원 배열, 0번 인덱스의 2차원 배열: 벽을 한번 부수고 이동 시
# 1번 인덱스의 2차원 배열: 벽을 부수지 않고 이동 시
visited = [[[1e10] * M for _ in range(N)] for _ in range(2)]

solution()

# 벽 부순 경우, 부수지 않은 경우 중 최소 거리
answer = min(visited[0][N-1][M-1], visited[1][N-1][M-1])

# 이동 불가시 -1 출력, 최소 거리 출력
if answer == 1e10:
    print(-1)
else:
    print(answer)

---

🔗 문제 링크

- https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다