💯Problem Solving
[BOJ] 2206 벽 부수고 이동하기
date
Aug 2, 2023
slug
boj-2206
author
status
Public
tags
Python
BOJ
summary
백준 2206번 문제풀이입니다.
type
Post
thumbnail
category
💯Problem Solving
updatedAt
Aug 2, 2023 04:42 AM
문제 링크
문제
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.
만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.
문제풀이
방문여부 배열을 벽을 부쉈는지 안부쉈는지로 나눠서 3차원 배열로 선언해준다.
queue에 현재 탐색하고 있는 방식이 벽을 부수고 가는지 아니면 그냥 가는지 여부와
이동거리를 같이 넣어준다.
만약에 다음 이동해야되는 곳이 범위 안에 있으면
다음 이동하는 곳이 현재 벽 부숨 여부에 따라 방문하지 않았던 곳이라면
만약 다음 이동하는 곳이 벽이라면 지금 벽을 부수지 않았으면
다음 이동하는 곳의 벽을 부쉈을때의 방문 여부를 true로 바꾸고 탐색
다음 이동하는 곳이 벽이 아니라면
현 벽 부숨 상태를 그대로 유지하면서 탐색
이렇게 구현하면 visited배열에 도착하는 queue의 원소는
벽을 부쉈을떄와 벽을 부수지 않았을때의 최단거리를 둘다가지고 있게된다.
마지막에 도착했을때 count를 리턴
파이썬 문제풀이 코드
import sys from collections import deque input = sys.stdin.readline N, M = tuple(map(int, input().split())) dx = [1, 0, -1, 0] # 동남서북 dy = [0, -1, 0, 1] visited = [[[False] * 2 for _ in range(M)] for _ in range(N)] # 방문배열 arr = [] for _ in range(N): li = [int(i) for i in input().strip()] arr.append(li) def bfs(): q = deque() # x, y, wall_count, count q.append((0, 0, 0, 1)) while q: y, x, wall_count, count = q.popleft() if y == N-1 and x == M-1: return count for i in range(4): if x+dx[i] < 0 or x+dx[i] >= M or y+dy[i] < 0 or y+dy[i] >= N: continue else: if visited[y+dy[i]][x+dx[i]][wall_count] == 0: if arr[y+dy[i]][x+dx[i]] == 1: if wall_count == 0: q.append((y+dy[i], x+dx[i], wall_count+1, count+1)) visited[y+dy[i]][x+dx[i]][1] = True else: continue elif arr[y+dy[i]][x+dx[i]] == 0: q.append((y+dy[i], x+dx[i], wall_count, count+1)) visited[y+dy[i]][x+dx[i]][wall_count] = True return -1 print(bfs())
시간복잡도
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
출력
첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.
4 4 0111 1111 1111 1110
-1