[백준] 2206번 벽 부수고 이동하기(python)

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

2206번: 벽 부수고 이동하기

 

1. 난이도 골드3 (🥇)

 

아 진짜 넘나리 어려웠는데 막상 이해하니 해볼만 한 것 같다.

 

3차원 list를 이용해서 벽을 부순적이 있는 지 없는 지를 확인해주면 된다.

 

 

2. 코드 분석

 

1. n,m, maps는 다른 문제와 동일하게 입력을 받는다.

 

2. 방문 여부를 확인하기 위해 visit 리스트를 만든다. 이때, 같은 행과 열의 크기를 가진 2층짜리 3차원 리스트를 만든다.

 

3.처음 위치를 1로 바꿔줌으로써 방문처리 해준다. 

from collections import deque

n,m = map(int,input().split())

maps = [list(map(int,input())) for _ in range(n)]

visit = [[[0]*2 for _ in range(m)] for _ in range(n)]
visit[0][0][0] = 1 #[행][열][층]

 

4. x(행) == n-1 and y(열) == m-1 일 경우 (목적지에 도착할 경우) visit에 있는 값을 return 해준다.

 

그게 아니라면 상하좌우를 하나씩 이동해준다.

 

def bfs(a,b,c):

  queue = deque()
  queue.append((a,b,c))

  while queue:
    x,y,z = queue.popleft()

    if x == n-1 and y == m-1:
      return visit[x][y][z]

    dx = [-1,1,0,0]
    dy = [0,0,-1,1]

 

5. 상하좌우로 움직인 좌표를 두 경우로 나누어 확인한다.

 

첫 번째, 벽을 만났으며 아직 벽을 부순적이 없는 경우 => maps[nx][ny]==1 and z == 0

 

이 경우에는 벽을 부술 것이기 때문에 1층으로 이동해 주고 visit에는 현재 위치의 cnt 값 + 1 해준 값을 넣어준다.

 

      if nx<0 or ny<0 or nx>=n or ny>=m:
        continue
      
      if maps[nx][ny]==1 and z == 0:
        visit[nx][ny][1] = visit[x][y][z] + 1
        queue.append((nx,ny,1))

 

두 번째, 벽을 만나지도 않았고 방문한 적도 없다면 그동안의 bfs와 동일하게 처리해준다.

 

elif maps[nx][ny]==0 and visit[nx][ny][z] == 0:
        visit[nx][ny][z] = visit[x][y][z] + 1
        queue.append((nx,ny,z))

 

7. while 문이 끝났다는 것은 n-1과 m-1에 도달하지 못했다는 것이기 때문에 return -1을 해주면 된다.

 

 

3. 전체 코드

from collections import deque

n,m = map(int,input().split())

maps = [list(map(int,input())) for _ in range(n)]

visit = [[[0]*2 for _ in range(m)] for _ in range(n)]
visit[0][0][0] = 1

def bfs(a,b,c):

  queue = deque()
  queue.append((a,b,c))

  while queue:
    x,y,z = queue.popleft()

    if x == n-1 and y == m-1:
      return visit[x][y][z]

    dx = [-1,1,0,0]
    dy = [0,0,-1,1]

    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
      
      if maps[nx][ny]==1 and z == 0:
        visit[nx][ny][1] = visit[x][y][z] + 1
        queue.append((nx,ny,1))

      elif maps[nx][ny]==0 and visit[nx][ny][z] == 0:
        visit[nx][ny][z] = visit[x][y][z] + 1
        queue.append((nx,ny,z))

  return -1

print(bfs(0,0,0))

 

 ㅠㅠ

 

4. 메모

원래 visit 하지 않은 경우마다 maps를 복사해서 결과값을 구하려고 시간초과가 발생했다. 데이터가 너무 커서 당연한 문제

 

또한 python에는 깊은 복사와 얕은 복사가 있다. copy.deepcopy 를 이용하면 시간이 오래걸리고, slicing을 이용하면 비교적 빠르긴 하지만 데이터가 너무 커서 또 시간초과가 발생한다.

 

참고링크 : https://blockdmask.tistory.com/576