[Python/BOJ] 백준 2206 벽 부수고 이동하기(BFS)

 

 

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

2206번: 벽 부수고 이동하기

 

 

 

 

🐾 20221031

 

 

🖌 어떤 생각?

 

1. 벽을 부쉈는지 안부쉈는지를 저장한는 변수가 필요하겠구나

그래서 덱에 3개의 수가  들어있겠구나

 

2. 토마토와 달리 숫자가 띄어쓰기 없이 입력되는데 어떻게 리스트 형태로 잘 만들 수 있을까?

 

3. 그래서 bfs를 어떻게 만들어야하지?!

 

 

 

💡 어떻게 해결하지?

 

1. 방문여부를 확인하면서 거리를 저장하는 배열 vis를 만들 때

벽의 부서짐 여부를 저장할 수 있도록 3차원 리스트로 만든다.

 

vis = [[[0]*2 for _ in range(m)] for __ in range(n)]

 

 

 

2. 토마토와 달리 숫자가 띄어쓰기 없이 입력되는데
어떻게 리스트 형태로 잘 만들 수 있을까?

-> list 함수만 있다면 당연히 가능하다. 

 

 

import sys
input = sys.stdin.readline
arr = [(list(map(int,list(input().strip()))))for _ in range(n)]

여기서 strip()은 앞과 뒤의 \n을 제거해주기 위해서 존재한다.

sys.stdin.readline은 \n을 함께 읽기때문이다. 

 

input()보다 sys.stdin.readline가 빨라서 이렇게 적었다.

 

위 코드를 자세하게 적어보자면

list(input().strip()) 은 들어온 숫자(11100)을 리스트화 한다. ['1', '1', '1', '0', '0']으로 만드는 것이다.

이는 str 이기에 int로 바꾸기위해 map함수를 이용해 int형으로 변환한다. 

그후 list로 형태를 변환한다. 

 

이를 n만큼 for문을 돌려 n줄을 입력받는다. 

 

 

 

 

 

 3. 그래서 bfs는?

 

-> 3번째 변수를 벽을 부순 여부를 나타내도록 한다. 

1일 때는 벽을 안부순 세계 

0일 때는 벽을 부순 세계

 

벽을 안부쉈고 벽이 있다면 벽을 부순다.

벽이 없고 가본적이 없다면 +1 해준다. 

 

나머지 경우 ->

벽을 부쉈고 벽이 있다면 못가는거지 뭐...

 

벽이 있고 가본 적이 있다면 안가는거지 뭐...

 

pop할 때마다 마지막 자리에 왔는지 검사해 왔다면 해당 vis값을 반환해준다. 

 

 

 

 

[코드]

from collections import deque
import sys
input = sys.stdin.readline

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

def bfs() :
    q= deque()
    vis = [[[0] * 2 for _ in range(m)] for __ in range(n)]
    q.append([0,0,1])
    vis[0][0][1] = 1
    while q :
        x,y,z = q.popleft()
        if x==n-1 and y == m-1 : 
            return vis[x][y][z]
        for i in range(4) :
            nx, ny = dx[i] + x,  dy[i] + y
            if 0<=nx<n and 0<=ny<m :
                if arr[nx][ny] == 1 and z == 1 : # 벽을 안뚫은 상태 
                    q.append([nx,ny,0])
                    vis[nx][ny][0] = vis[x][y][1]+1
                elif arr[nx][ny] == 0 and vis[nx][ny][z]==0: # arr에 갈 수 있고 간적없다면
                    vis[nx][ny][z] = vis[x][y][z]+1
                    q.append([nx,ny,z])
    return -1


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

arr = [(list(map(int,list(input().strip()))))for _ in range(n)]
print(bfs())

 

 

vscode에서 안돌아간다..!

파이썬이 이만큼 느리다는 뜻인가

 

 

https://replit.com/

The collaborative browser based IDE

 

 

 

빠르게 잘 나온다^^!

 

 

 

 

 

 

백준에서는 같은 코드를 pypy3로 컴파일하니까 훨씬 빠르다

 

 

 

 

 

 

 

 

음? 

vscode에서도 이 코드로 하니까 돌아간다.

 

from collections import deque 

dx = [0,1,0,-1]
dy = [1,0,-1,0]
                
                
if __name__=="__main__" :
    n,m = map(int,input().split())
    mp = [list(map(int,input())) for _ in range(n)]
    # [1]은 벽은 안깬 vis, [0]은 벽을 깬 방문 확인 배열  
    vis = [[[0]*2 for _ in range(m)] for _ in  range(n)]
    # 벽을 안깬 첫번째 위치 방문 표시 
    vis[0][0][1] = 1 
    q = deque()
    q.append([0,0,1])
    
    while q :
        x,y,z = q.popleft()
        # 목표 도착 
        if x == n-1 and y == m-1 :
            print(vis[x][y][z])
            exit(0)
        for i in range(4) :
            nx,ny = x + dx[i], y + dy[i]
            if 0<=nx<n and 0<=ny<m :
            	#  갈수가 없는데 벽을 아직 안깼다면 
                if mp[nx][ny]==1 and z == 1 :
                	# 방문 거리를 vis에 잘 저장 
                    vis[nx][ny][0] = vis[x][y][1]+1
                    q.append([nx,ny,0])
                # 갈수가 있는데 가본적이 없다면 
                elif mp[nx][ny]==0 and vis[nx][ny][z]==0 :
                    vis[nx][ny][z] = vis[x][y][z]+1
                    q.append([nx,ny,z])
    print(-1)

 

 

 

 

<참고 코드>

 

https://pacific-ocean.tistory.com/348

[백준] 2206번(python 파이썬)