[BOJ] 2206. 벽 부수고 이동하기

 

백준 문제 주소 :

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

 

DFS, BFS의 머나먼 조상님 미로 문제에 조건 한 가지를 추가한 문제였습니다.

미로에서 단 한번!!! 벽을 부술 수 있다는 건데요. 하 ㅠㅠ 너무 힘들었어요

보이나요 제 노력... ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

 

 

처음은 그냥 itertools 라이브러리의 combinations을 사용해서

1이 하나씩 사라진 모든 2차원 배열을 만들었습니다.

 

바로 메모리초과~~^^

 

그래서 선택한 방법이 한개 뚫는 것을 장착식 아이템처럼 1로 만들어 놓고

뚫었을 때, 0으로 만들어 줬습니다.

 

다음은 시간초과~~^^

 

나한테 왜 그래 ㅠㅠ... 그래서 조건문을 추가해서 시간을 줄였습니다.

result받는순간 break하는 걸루, bfs로 풀어서 사실 이게 큰 의미는 없지만 조금은 줄여지거든요!

그리고 자기 자신을 1로 만들고 이동을 시작하는데, 0일때만 이동 가능하게 해보았습니다.

당연히 벽을 뚫는 그 순간은 2차원 배열에 그 뚫은 자리를 0으로 만들어 줬구요.

 

그렇게 하니까 53퍼까지 성공!

 

기분좋아서 더 끄적여보다가 발견한 반례.....

8 8
01000100
01010100
01010100
01010100
01010100
01010100
01010100
00010100

이 안된다는 것... ㅠ

밑으로 1을 뚫고 먼저 간 애들이 0자리를 1로 만들어버려서

밑에 0을 찍고 간 애들이 1에 막혀서 못 간다는 것이었죠 ㅠㅠ

 

그래서 차원을 다르게 만들어 봤습니다. 2차원 배열을 두가지 만들고,

1을 뚫었을 때랑, 0일 때 다르게 만들었고, 성공..(?) 하는 듯 보였지만

또 시간초과! 두가지 배열 모두 보려니까 시간초과가 났어요.. ㅠㅠ

 

다시 한번 더 시간을 줄이기 위해, 들어가는 자기 자리를 1로 만드는게 아니라

갈 예정인 곳을 1로 만들어주었습니다.

그렇게 시간초과를 뚫고 가는 듯 보였는데!!

100%에서 또 틀리는거 있죠..?

잘못본건가 싶어서 3번이나 똑같이 돌렸어요... ㅋㅋㅋㅋㅋㅋㅋㅋ

 

마지막 반례 찾아낸 것은

1 1
0

이 때, 답은 1이 나와야하는데 -1이 나온다는 것... 

갈예정인 곳만 보다 보니 이렇게 된 거죠 ㅠㅠ

그래서 조건하나 추가하고 끝~~~ 마쳤습니다 ㅎㅎ

성공!!

from copy import deepcopy
from collections import deque

def solution():
    def go(N, M, start, cnt):
        for i in range(4):
            rx = start[0] + dx[i]
            ry = start[1] + dy[i]
            if rx == N-1 and ry == M-1:
                result.append(cnt)
                return

            if  N > rx > -1 and M > ry > -1:
                if start[2] == 0:
                    if all[start[2]][rx][ry] == 0:
                        visit_plan.append((rx, ry, start[2]))
                        all[start[2]][rx][ry] = 1
                        all[start[2] + 1][rx][ry] = 1
                    else:
                        visit_plan.append((rx, ry, start[2]+1))
                if start[2] == 1:
                    if all[start[2]][rx][ry] == 0:
                        visit_plan.append((rx, ry, start[2]))
                        all[start[2]][rx][ry] = 1

    n, m = map(int, input().split())
    arr = [[int(j) for j in input()] for i in range(n)]
    another = deepcopy(arr)
    all = [arr, another]
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]

    result = []
    cnt = 1
    visit_plan = deque([(0, 0, 0)])
    all[0][0][0] = 1
    all[1][0][0] = 1
    if n == 1 and m == 1:
        print(1)
    else:
        while visit_plan :
            cnt += 1
            # print(visit_plan)
            for _ in range(len(visit_plan)):
                go(n, m, visit_plan.popleft(), cnt)
                if result :
                    print(result[0])
                    break
            if result:
                break
        else :
            print("-1")
solution()