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

1. 시간 초과가 뜬 코드

다음 코드는 모든 1을 하나씩 0으로 바꿔가며 bfs를 진행해서 최단거리를 찾는 방법이다.

이 방법은, 답은 맞지만 시간초과가 뜬다.

사실 풀면서도 시간 초과 뜰 거라고 생각하긴 했음... 그러면서도 다른 방법 생각안하고 끝까지 이걸로 해본 내가 참..ㅋㅋㅋㅋ 웃김.

import copy
n, m = map(int, input().split())
graph1 = []
for _ in range(n):
    graph1.append(list(map(int, input())))

from collections import deque

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

def bfs(x, y, graph):
    queue = deque()
    graph[x][y] = 2
    queue.append([x, y])
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] + 1
                queue.append([nx, ny])
    return graph[n-1][m-1]

arr = []
graph_ = copy.deepcopy(graph1)
for i in range(n):
    for j in range(m):
        if graph_[i][j] == 1:
            graph_ = copy.deepcopy(graph1)
            graph_[i][j] = 0
            value = bfs(0, 0, graph_)
            if value == 0:
                pass
            else:
                arr.append(value)
            graph_[i][j] = 1

if len(arr) != 0:
    print(min(arr)-1)
else:
    print(-1)

 

 

2. 정답?

일단, 질문하기의 제목들을 통해 3차원으로 둬서 벽이 뚫린 경우와 아닌 경우를 구분하는 풀이가 대부분이라는 걸 알았다.

어떻게 하라는 건지 잘 감이 잡히지 않았지만 이를 단서로 좀 더 생각해보기로 한다. 

 

그러나 도저히 모르겠어서 인터넷 코드를 찾아봤다.

그리고 다시 생각하고 구현했다.

이 문제도 다시 풀어봐야겠다.. 세상엔 어려운 문제가 너무 많아..

n, m = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, input())))
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]

from collections import deque

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

def bfs():
    queue = deque()
    queue.append([0,0,0])
    visited[0][0][0] = 1
    while queue:
        x, y, z = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == 0 and visited[nx][ny][z] == 0:
                    visited[nx][ny][z] = visited[x][y][z] + 1
                    queue.append([nx, ny, z])
                elif graph[nx][ny] == 1 and z == 0:
                    visited[nx][ny][1] = visited[x][y][z] + 1
                    queue.append([nx, ny, 1])
            if x == n -1 and y == m -1:
                return visited[x][y][z]
    return -1


print(bfs())