[2206] 벽 부수고 이동하기 (Python)

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

2206번: 벽 부수고 이동하기

---

이 문제는 정말 오래 삽질한 문제다. 진짜 진짜 너무 어려워서 저거 푼다고 며칠동안 끙끙댔다.

한 일주일동안 저거 때문에 다른 문제를 못 풀었던 기억.. 

이렇게 사진으로 보면 안그런거같지만 로컬에서 계속 돌려서 그렇지 진짜 한 5일은 붙잡고 있었음. 겨우 힌트보고 해결했고 알고리즘 스터디하면서 친구들한테 풀이 설명해주는거 조차 너무 어려웠음

 

문제

위 문제를 간단하게 정리하면 다음과 같다.

 

• n*m 의 맵에 위치 정보 (0 : 이동가능 / 1:벽)
• (1,1)에서 (n,m)까지 최단 경로로 이동
  • 맵에서 가장 적은 개수의 칸을 지나는 경로 (시작칸과 끝칸 포함)
• 이동하는 도중에 1개의 벽을 부수고 이동 가능

 

 

풀이 1 : 시간초과

처음에는 브루트포스로 모든 경우를 체크하려고 했다. 하지만 시간초과로 실패~!

몇 달전에 푼거라 정확한 과정은 생각안나는데 연습장에 적어놓은거 보면 아래와 같이 풀었던듯

 

1) 1이 있는 모든 칸을 1번씩 삭제해보며 탐색

2) 탐색 시 최단 경로 길이 len을 저장

3) 다음 탐색에서 len보다 큰 값이 나오면 탐색 stop, 다음 칸 삭제

 

저 당시에는 문제를 많이 안풀어봤을 때라 몰랐는데 지금 보니까 딱봐도 시간초과 날 수 밖에 없는 풀이방법이다.

 

 

 

풀이 2 : 드디어 통과

진짜 너무 막막했는데 어느 천사분의 힌트를 보고 해결했다. 이거없었으면 못 풀었을듯

위 글에서 기본 원리를 생각해보자면

이 문제는 가중치가 없는 최단경로이므로 bfs로 해결해야하고 내가 풀었던 브루트포스 방법으로는 최악의 경우 (1000*1000)^2 의 반복이 된다.

 

또한, 칸마다 방문 체크하는 방식으로는 풀 수 없다.

0이 이동가능한 위치이고 1이 벽이라고 했을 때, 0 → 0 , 0 → 1 , 1 → 0 은 이동이 가능하고 1 → 1 은 이동이 불가능하다.

하지만 0 → 1 → 0 , 1 → 0 → 1 의 경우, 위에 해당하지만 이동이 불가능하므로 칸마다 방문체크를 하는 방법은 옳지 않다.

0 → 1 → 0 는 되는 것처럼 보일 수 있지만 이미 1로 이동하여 벽을 부순적 있으므로 벽을 부수지 않은 경우와 다르게 표시해야한다.

즉, 벽이 부순 상태에서 벽을 부수지 않은 상태로 이동이 불가능하다.

 

 

 

따라서 벽을 부수지 않은 상태와 벽을 부순 상태의 최단거리를 각자 따로 2차원 배열에 저장해야한다.

경로를 탐색할 때, bfs로 주위를 탐색하고 경우에 따라 다르게 생각해야한다.

 

(1) 벽을 부수지 않은 상태에서 이동할 때

• 0으로 이동 : 벽을 부수지 않은 상태 유지하고 이동
• 1으로 이동 : 벽을 부순 상태로 이동

(2) 벽을 부순 상태에서 이동할 때

• 0으로 이동 : 벽을 부순 상태 유지하고 이동
• 1으로 이동 : 이동 불가

bfs를 수행할 때, queue에 벽을 부순 적이 있는지와 위치좌표값을 함께 넣어 체크해봐야한다.

이와 같이 최단거리를 구한 후, (n-1, m-1) 위치에 도달했을 때의 값이 최단 경로가 된다.

난 (0,0) -> (n-1,m-1)로 생각하여 구했다. (1,1)->(n,m)으로 생각하여 풀었다면 (n,m) 위치에 도달했을 때의 값이 최단 경로이다.

 

 

이해하기 쉽게 이동의 경우를 그림 이용해 예시를 보여주겠다.

먼저 graph 배열은 다음과 같다.

 

(1) 벽을 부수지 않은 상태에서 0으로 이동

일반적인 bfs 방식으로 이동하여 벽을 부수지 않은 상태 배열에 값을 저장하면 된다.

 

(2) 벽을 부수지 않은 상태에서 1로 이동

벽을 부쉈다면 벽을 부순 상태 배열에 값을 저장한다.

 

(3) 벽을 부순 상태에서 0으로 이동

벽을 부순 상태에서 주위의 이동하여 값을 저장하면 된다.

 

(4) 벽을 부순 상태에서 1로 이동은 할 수 없다.

 

 

위와 같은 이동 방식으로 구현하면 된다!

 

 

 

코드

구현 순서를 간단하게 요약하면 아래 더보기과 같다.

1. 3차원 배열 wall을 생성
   • wall[i][j][0] : 벽을 부수지 않고 이동하는 최단 경로 배열
   • wall[i][j][1] : 벽을 부수고 이동하는 최단 경로 배열
     • wall[i][j][1] 에서 wall[i][j][0] 으로 이동할 수 없음
2. bfs 함수 생성
   1. 출발위치 wall[0][0][0]의 x,y,z인 0,0,0을 queue에 넣기
   2. 반복문
      1. queue에서 x, y, z 를 꺼냄
      2. 현재위치가 도착지점일 경우, 도착지점의 최단경로인 wall[x][y][z] 반환
      3. 현재 위치( wall[x][y][z] )의 상하좌우 탐색
      4. 다음 위치가 벽이 아닐 경우 ( 0 → 0 or 1 → 0 )
         • 다음 위치 wall[nx][ny][z] 는 현재 위치 wall[x][y][z] + 1
         • nx, ny, z 를 queue에 넣기
      5. 현재 위치가 벽X, 다음 위치가 벽이고( 0 → 1 ) , 벽 부수기 기록이 없는 경우
         • 다음 위치 wall[nx][ny][1] 는 현재 위치 wall[x][y][z] + 1
         • nx, ny, 1 을 queue에 넣기
      6. 현재 위치와 다음 위치 모두 벽일 경우 ( 1 → 1 ) : 불가능
   3. 도달하지 못했을 경우 -1를 반환

 

코드는 다음과 같다.

import sys
from collections import deque

# 입력
n,m = map(int,sys.stdin.readline().split())
graph=[]    # 맵
wall=[[[0]*2 for _ in range(m)] for _ in range(n)]     
for i in range(n):
    graph.append(list(map(int,sys.stdin.readline().rstrip())))

# bfs 함수
dx=[-1,1,0,0]
dy=[0,0,-1,1]
def bfs(wall,x,y):
    # 큐에 출발 위치 삽입
    queue=deque()
    queue.append((x,y,0))
    # 출발 위치 방문 처리
    wall[x][y][0]=1
    # 탐색
    while queue:
        x,y,z=queue.popleft()
        if x==n-1 and y==m-1:
            return wall[x][y][z]
        # 상하좌우 탐색
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx<0 or ny<0 or nx>=n or ny>=m:
                continue
            # 다음 위치가 벽이 아닐 경우 ( __ -> 0 )
            if graph[nx][ny]==0 and wall[nx][ny][z]==0:
                wall[nx][ny][z] = wall[x][y][z]+1
                queue.append((nx,ny,z))
            # 위치가 0 -> 1로, 벽부수기 기록 없을 때
            elif graph[nx][ny]==1 and z==0 and wall[nx][ny][1]==0:
                wall[nx][ny][1] = wall[x][y][z]+1
                queue.append((nx,ny,1))
            # 위치 1 -> 1은 불가능

    # 도달하지 못했을 경우
    return -1

# main코드
print(bfs(wall,0,0))