[백준 2206번] 파이썬 - 벽 부수고 이동하기

http://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

 

# 조건

• NxM 행렬로 표현되는 맵이 있다.
• 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다.
• (1,1)에서 (N, M)의 위치까지 이동하려 하는데, 이 때 최단 경로로 이동하려 한다.
• 최단 경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 시작하는 칸과 끝나는 칸도 포함해서 센다.
• 만약 이동하는 도중 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 한 개 까지 부수기 가능
• 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

 

# 접근 방법

• 맵을 받아준 후 벽돌이 들어있는 인덱스를 리스트로 받아준다.
• 벽돌을 안 부순 맵 ~ 벽돌 인덱스를 돌며 하나씩 부순 맵을
• BFS를 이용하여 탐색해준다.
• 시작점 +1을 하여 도착지에 도달하였다면 결괏값에 기록해준다.
• 벽돌을 부순 맵을 사용할 때는 deepcopy 내부 모듈을 이용해 준다.
• 맵을 받아줄 때 공백이 없이 들어오므로 split 사용 x

 

시간 초과

• 모든 벽돌 체크시 시간초과

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from copy import deepcopy  
from collections import deque  
  
# 맵 인자로 받아주기  
def bfs(copy_map):  
    global result  
    q = deque()  
    q.append((0,0))  
    copy_map[0][0] = 1  
    while q:  
        sti, stj = q.popleft()  
        if sti == N-1 and stj == M-1:  
            if copy_map[sti][stj] < result:  
                result = copy_map[sti][stj]  
        for k in range(4):  
            ni, nj = sti + di[k], stj + dj[k]  
            # 범위 내이고 방문하지 않았다면  
            if ni < 0 or nj < 0 or ni >= N or nj >=M or copy_map[ni][nj] != 0:  
                continue  
            q.append((ni,nj))  
            copy_map[ni][nj] = copy_map[sti][stj] + 1  
  
  
N, M = map(int, input().split())  
  
map = [[*map(int, input().rstrip())] for _ in range(N)]  
brick = []  
for i in range(N):  
    for j in range(M):  
        if map[i][j] == 1:  
            brick.append((i,j))  
# 델타 함수  
di, dj = [1,-1,0,0], [0,0,1,-1]  
  
# 기본 맵으로 bfs 수행  
result = float('inf')  
bfs(map)  
  
# 벽돌 부수면서 체크  
for i,j in brick:  
    broke_map = deepcopy(map)  
    broke_map[i][j] = 0  
    bfs(broke_map)  
if result < float('inf'):
	print(result)
else:
	print(-1)

• 따라서, 조금 생각을 달리해주면 될 것 같다.
• 모든 벽을 반복문을 통해 도는 것이 아닌
• bfs를 돌며 벽을 부순 경우를 체크해주면 될 것 같다.
• 3차원 행렬을 이용하여 벽을 부순 경우와 부수지 않은 경우를 구분한다.
  • 3차원 배열에 0번 인덱스 -> 벽을 부수지 않은 경우
  • 1번 인덱스 -> 벽을 부순 경우로 체크해준다.
• 벽이 아닌 경우를 만났을 때는
  • 벽을 파괴한 경로가 존재할 경우 추가 x
  • 파괴하지 않은 경우, 파괴하지 않은 경로가 이미 지나갔다면 방문 x

import sys  
sys.stdin = open('input.txt')  
from collections import deque  
  
# 맵 인자로 받아주기  
def bfs(map):  
    global result  
    q = deque()  
    q.append((0, 0, 0))  
    visited = [[[0]*2 for _ in range(M)] for _ in range(N)]  
    # 시작점의 경우 0번 -> 파괴하지 않은 경로에 + 1을 해준다.  
    visited[0][0][0] = 1  
    while q:  
        sti, stj, flag = q.popleft()  
        if sti == N-1 and stj == M-1:  
            if visited[sti][stj][flag] < result:  
                result = visited[sti][stj][flag]  
        for k in range(4):  
            ni, nj = sti + di[k], stj + dj[k]  
            # 범위 내이고 방문하지 않았다면  
            if ni < 0 or nj < 0 or ni >= N or nj >=M:  
                continue  
            # 벽을 만났고 아직 벽을 부수지 않았다면  
            if map[ni][nj] == 1 and not flag:  
                # 벽을 부순 경로 -> 1번 인덱스에  
                # 벽을 부수지 않았던 경로 + 1을 해준다.                visited[ni][nj][1] = visited[sti][stj][0] + 1  
                q.append((ni,nj, 1))  
            # 벽이 아니고 방문하지 않았다면 추가  
            # 방문 체크는 flag를 통하여            # 이미 벽을 부수고 지나간 지점이 있다면 추가 x  
            # 이미 벽을 부수지 않고 통과한 경로가 있다면 마찬가지로 추가 x            
            elif map[ni][nj] == 0 and visited[ni][nj][flag] == 0:  
                visited[ni][nj][flag] = visited[sti][stj][flag] + 1  
                q.append((ni,nj,flag))  
  
  
N, M = map(int, input().split())  
map = [[*map(int, input())] for _ in range(N)]  
brick = []  
for i in range(N):  
    for j in range(M):  
        if map[i][j] == 1:  
            brick.append((i,j))  
# 델타 함수  
di, dj = [1,-1,0,0], [0,0,1,-1]  
  
# 기본 맵으로 bfs 수행  
result = float('inf')  
bfs(map)  
  
if result < float('inf'):  
    print(result)  
else:  
    print(-1)