[백준] BFS + Depth & 두 가지의 visited / 벽 부수고 이동하기

 

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

2206번: 벽 부수고 이동하기

 

 

나의 코드

inputs=[]
[N,M] = list(map(int,input().split()))

for _ in range(N):
    inputs.append(list(map(int,input())))

from collections import deque

def solution(N, M, inputs):
    if N==1 and M==1:
        return 1

    cand = deque()
    visited = [[[0,0] for _ in range(M)] for _ in range(N)] #3차원의 visited array
    cand.append(((0,0),0))
    visited[0][0][0] = 1

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

    while cand:
        ((x,y),i) = cand.popleft()
        for k in range(4):
            cx = x + dx[k]
            cy = y + dy[k]
            if cx<0 or cx>N-1 or cy<0 or cy>M-1:
                continue
            else:
                if inputs[cx][cy] == 0 and visited[cx][cy][i]==0:
                    if cx == N-1 and cy == M-1:
                        return visited[x][y][i] + 1
                    cand.append(((cx,cy),i))
                    visited[cx][cy][i] = visited[x][y][i] + 1

                elif inputs[cx][cy] == 1 and i==0:
                    cand.append(((cx,cy),1))
                    visited[cx][cy][1] = visited[x][y][0] + 1

    return -1

print(solution(N,M,inputs))

 

1. BFS + Depth !!를 효율적으로 구현

 visited[cx][cy][i] = visited[x][y][i] + 1

 

2. visited를 두 유형으로 나누어야 한다(visited array를 3차원으로 표현) → 벽을 부수기 전 & 벽을 부순 후.

- 이유:

결국 방문배열이란 것은, bfs에서 '모든 경우'를 살펴보며 진행할 때, 같은 행위를 두번하면 비효율적이니 그걸 막기 위해 사용합니다.

따라서 방문배열은 '모든 경우'를 나타낼 수 있어야 합니다. 일반적인 bfs 문제에서 모든 경우는 결국 '이 위치에 이미 왔었다' 입니다.

따라서 그냥 2차원 방문배열로 나타내면 되는거구요.

이 문제에서 모든 경우는 말로 설명하자면 '해당 위치에 벽을 부순 상태로 이미 왔었거나, 해당 위치에 아직 벽을 부수지 않은 상태로 이미 왔었다.' 정도가 되겠습니다.

따라서 이걸 표현하기 위해 3차원 배열로 나타낸거구요.

이런식으로 모든 경우를 나타낼 수 있는 방문배열을 만들지 않을 경우 다음과 같은 문제가 발생합니다.

출처: https://www.acmicpc.net/board/view/67446

 

 - 추가 설명:

모든 작업을 한 번의 BFS 탐색을 통해 처리해야했기 때문에, 최적의 벽을 '탐색'하는 것보다는 '기록'하는 방식이 필요했다.

그리고 3차원 배열을 통해서 이 문제를 해결할 수 있었다.

visited에는 이미 우리에게 친숙한 2차원 배열의 각 인덱스 [x][y]뿐 아니라 w라는 값을 하나 더 만들어서 (x, y)까지 오는 과정에서 벽을 뚫은 경우와 그렇지 않고 온 경우를 모두 기록해준다. (각각 1번 인덱스와 0번 인덱스에 기록)

다시 말해, visited[x][y][0]에 (x, y)까지 벽을 뚫지 않고 왔을 때 걸린 거리(시간)을 기록해준다.

반대로, visited[x][y][1]에는 (x, y)까지 오는 데 벽을 한 번이라도 뚫고 온 경우 걸린 거리(시간)을 기록해준다.

출처: https://seongonion.tistory.com/107

 

추가: https://nahwasa.com/entry/BFS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%84%88%EB%B9%84-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89-%EB%B0%B0%EC%97%B4-BFS-%EA%B7%B8%EB%9E%98%ED%94%84-BFS

 

3. 이하 코드는 항상 요긴하게 씁사..

        for k in range(4):
            cx = x + dx[k]
            cy = y + dy[k]
            if cx<0 or cx>N-1 or cy<0 or cy>M-1:
                continue

 

 

- 배운 점: BFS문제 다 똑같지 않다. 변형 테크닉이 어렵고, 익숙해지면 아이디에이션 생각보다 간단하다.

 

 

---

나의 방황 기록

초기 코드1: Depth를 2 type으로 구분하지 않고 1 type으로 몰아갔다..

→ 당연히 틀림 (초반에는 경로가 비효율적이더라도 벽을 아직 부수지 않아서 최종 목적지까지 다다를 수 있는 경로가 배제됨)

inputs=[]
[N,M] = list(map(int,input().split()))

for _ in range(N):
    inputs.append(list(map(int,input())))

from collections import deque

def solution(N, M, inputs):

    cand = deque()
    cand.append(((0,0),0))
    inputs[0][0] = 1

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

    while cand:
        ((x,y),i) = cand.popleft()
        for k in range(4):
            cx = x + dx[k]
            cy = y + dy[k]
            if cx<0 or cx>N-1 or cy<0 or cy>M-1:
                continue
            else:
                if inputs[cx][cy] == 0:
                    inputs[cx][cy] = inputs[x][y]+1
                    if cx == N-1 and cy == M-1:
                        return inputs[cx][cy]
                    cand.append(((cx,cy),i))
                elif inputs[cx][cy] == 1:
                    if i == 0:
                        inputs[cx][cy] = inputs[x][y]+1
                        cand.append(((cx,cy),1))
    
    return -1

print(solution(N,M,inputs))

 

초기 코드2: visited 내역을 queue의 각 원소마다 포함해줬다

→ 예상한 대로 시간초과... 애초에 이렇게 풀 수 있는 문제 거의 없음

→ 조건 추가된 depth 계산은, 무조건 이 방식 말고 다른 방식을 떠올려야 함

(ex. visited array를 별도로 생성하여 0->1->2.. 이런 식의 표현을 베이스로 깔거나(이후 변형) / 조건 잘 따져서 global queue(set)을 생성하거나 등등. )

inputs=[]
[N,M] = list(map(int,input().split()))

for _ in range(N):
    inputs.append(list(map(int,input())))

from collections import deque

def solution(N, M, inputs):
    if N==1 and M==1:
        return 1
    
    cand = deque()
    cand.append(((0,0),0,[(0,0)]))

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

    while cand:
        ((x,y),i,visit) = cand.popleft()
        for k in range(4):
            cx = x + dx[k]
            cy = y + dy[k]
            if (cx<0 or cx>N-1 or cy<0 or cy>M-1) or ((cx, cy) in visit):
                continue
            else:
                if inputs[cx][cy] == 0:
                    if cx == N-1 and cy == M-1:
                        return len(visit) + 1
                    cand.append(((cx,cy),i, visit+[(cx,cy)]))
                elif inputs[cx][cy] == 1:
                    if i == 0:
                        cand.append(((cx,cy),1,visit+[(cx,cy)]))
    
    return -1

print(solution(N,M,inputs))