새로운 블로그로 이전 작업을 진행하고 있어 포스트가 새로 작성되고 있지 않습니다.

빠른 시일 내에 새로운 블로그로 인사드리겠습니다.

새로운 블로그 : https://unho.vercel.app/

본문 바로가기
알고리즘 문제풀이/Python

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

by 언호 2022. 8. 15.

📖 문제


🧑🏻‍💻 풀이 과정

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번: 벽 부수고 이동하기

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로

www.acmicpc.net

 

 

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

'알고리즘 문제풀이 > Python' 카테고리의 다른 글

[백준] 1944 복제 로봇  (0) 2022.08.17
[백준] 1700 멀티탭 스케줄링  (0) 2022.08.16
[백준] 1504 특정한 최단 경로  (0) 2022.07.30
[백준] 1719 택배  (0) 2022.07.18
[백준] 6087 레이저 통신  (0) 2022.07.17

댓글