[파이썬] 백준 2206 : 벽 부수고 이동하기 (골드3)

[파이썬] 백준 2206 : 벽 부수고 이동하기 (골드3)

 

2206번: 벽 부수고 이동하기

---

문제

---

풀이

 

0. 방향성 생각

• 벽을 한개까지 부술 수 있다.
• 벽을 부순 상태 / 부수지 않은 상태 2가지로 나눈다.
• visit 배열의 차원을 하나 늘린다.
• 방향으로 나누는 state가 아니어서 위로 쌓는 방식으로 visit 층수를 늘린다.

1. 입력

from collections import deque
import sys
input = lambda: sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(map(int,input())) for _ in range(h)]
visit = [[[-1]*w for _ in range(h)] for _ in range(2)]
dire = [(1,0),(0,1),(-1,0),(0,-1)]

• 2층짜리 격자 visit을 만들어준다.
• 4가지 방향 정의

2. BFS

q = deque([(0,0,0)])
visit[0][0][0] = 1
while q:
    x,y,t = q.popleft() # 벽을 t개까지 부수상태
    
    for dx,dy in dire:
        nx = x + dx
        ny = y + dy
        
        if 0<=nx<w and 0<=ny<h and visit[t][ny][nx] == -1: # 방문안했으면
            if not arr[ny][nx]: # 그냥 갈 수 있는 경우
                visit[t][ny][nx] = visit[t][y][x] + 1 # 옆으로 이동
                q.append((nx,ny,t))

            elif t == 0 and arr[ny][nx] == 1: # 벽을 안뚫은 경우 다음칸이 벽일 때
                visit[1][ny][nx] = visit[0][y][x] + 1
                q.append((nx,ny,1))

• 큐에 좌표와 현재 탐색중인 말의 상태 t를 넣어준다
• t = 0 : 벽 안부순 상태 / t = 1 : 벽 부순상태
• inner / not visit - > 벽을 만난 경우 / 만나지 않은 경우
• 벽을 만나지 않은 경우에는 visit + 1 을 해주고
• 벽을 만난 경우에는 t = 0인 경우에만 탐색이 가능하게 해주고 t를 1로 변경해준다.

3. 출력

answer = [visit[i][-1][-1] for i in range(2)]
print(max(answer) if -1 in answer else min(answer))

• 벽을 안부수고 도착지점에 도달한 경우 / 벽을 부수고 도착지점에 도달한 경우
• 두 가지중 작은 경우를 출력한다.

 

---

전체코드

from collections import deque
import sys
input = lambda: sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(map(int,input())) for _ in range(h)]
visit = [[[-1]*w for _ in range(h)] for _ in range(2)]
dire = [(1,0),(0,1),(-1,0),(0,-1)]

q = deque([(0,0,0)])
visit[0][0][0] = 1
while q:
    x,y,t = q.popleft() # 벽을 t개까지 부수상태
    
    for dx,dy in dire:
        nx = x + dx
        ny = y + dy
        
        if 0<=nx<w and 0<=ny<h and visit[t][ny][nx] == -1: # 방문안했으면
            if not arr[ny][nx]: # 그냥 갈 수 있는 경우
                visit[t][ny][nx] = visit[t][y][x] + 1 # 옆으로 이동
                q.append((nx,ny,t))

            elif t == 0 and arr[ny][nx] == 1: # 벽을 안뚫은 경우 다음칸이 벽일 때
                visit[1][ny][nx] = visit[0][y][x] + 1
                q.append((nx,ny,1))
                
answer = [visit[i][-1][-1] for i in range(2)]
print(max(answer) if -1 in answer else min(answer))

 

코멘트

웰노운은 10분 이내로 줄이기.... 약간 느리다