[Baekjoon][2206] 골드3 벽 부수고 이동하기 - Python

🧱 벽부수고 이동하기

• 시간제한: 2초
• 메모리 제한: 192MB

📄 문제

• N x M의 행렬로 표현되는 맵이 있다. 
• 맵에서는 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다.
• 당신은 (1,1) 에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다.
• 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.
• 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.
• 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
• 맵이 주어졌을 때, 최단 경로를 구해내는 프로그램을 작성하시오.

입력

• 첫 줄에 N(1 <= N <= 1000), M(1 <= M <= 1000)이 주어진다.
• 다음 N개의 줄에  M개의 숫자로 맵이 주어진다.
• (1,1)과 (N, M)은 항상 0이라고 가정하자.

출력

• 첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

💡 문제 접근 아이디어

• (1, 1)과 (N, M) 각각 하, 우와 상, 좌가 1인 경우 == -1
• 가다가 길이 끊기는 경우 == -1
• DFS 알고리즘

 

❌ 2% 틀렸습니다.

• 너무 단순하게 예제 코드에만 맞춰서 생각한 것 같다.
• 다시 생각해보자.
• DFS가 아니라 BFS로 풀어야 하는게 맞는 것 같음! 

from sys import stdin

input = stdin.readline

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

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

# (1,1)과 (N,M)이 1로 가로막혀 있는지 확인
start = walls[0][1] and walls[1][0]
end = walls[N-1][M-2] and walls[N-2][M-1]

if start and end:
    print(-1)
    exit()


def dfs(graph, start):
    # start (x, y, value, walls-flag)
    stack = [start]

    # directions
    directionsX = [1, -1, 0, 0]
    directionsY = [0, 0, -1, 1]

    while stack:
        x, y, value, flag = stack.pop()
        # print(x, y, value, flag)
        # for g in graph:
        #     print(g)
        # print()

        graph[x][y] = min(value, graph[x][y]) if graph[x][y] > 1 else value

        for i in range(len(directionsX)):
            nx, ny = x + directionsX[i], y + directionsY[i]
            if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] in [0, 1]:
                if flag:
                    if graph[nx][ny] == 0:
                        stack.append((nx, ny, value + 1, flag))
                else:
                    if graph[nx][ny] == 1:
                        stack.append((nx, ny, value + 1, True))
                    else:
                        stack.append((nx, ny, value + 1, flag))
    return graph

result = dfs(walls, (0, 0, 2, False))

if result[N-1][M-1] > 1:
    print(result[N-1][M-1] - 1)
else:
    print(-1)

 

❌ 메모리 초과 >> 이런,,

• visited check할때 set 사용, 4 tuple 사용 등 이슈로 메모리 초과가 난 것 같다는 예상 >> 3차원 배열로 visited 선언해서 방문 체크로 변경

from sys import stdin
from collections import deque

input = stdin.readline

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

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

# (1,1)과 (N,M)이 1로 가로막혀 있는지 확인
start = walls[0][1] and walls[1][0]
end = walls[N-1][M-2] and walls[N-2][M-1]

if start and end:
    print(-1)
    exit()


def bfs(graph, start):
    # start (x, y, value, walls-flag)
    queue = deque([start])

    # directions
    directionsX = [-1, 1, 0, 0]
    directionsY = [0, 0, 1, -1]

    while queue:
        x, y, value, flag = queue.popleft()
        # print(x, y, value, flag)
        # for g in graph:
        #     print(g)
        # print(graph[x][y], value)
        # print()

        graph[x][y] = min(value, graph[x][y]) if graph[x][y] > 1 else value

        for i in range(len(directionsX)):
            nx, ny = x + directionsX[i], y + directionsY[i]
            if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] in [0, 1]:
                if flag:
                    if graph[nx][ny] == 0:
                        queue.append((nx, ny, value + 1, flag))
                else:
                    if graph[nx][ny] == 1:
                        queue.append((nx, ny, value + 1, True))
                    else:
                        queue.append((nx, ny, value + 1, flag))
    return graph

result = bfs(walls, (0, 0, 2, False))

if result[N-1][M-1] > 1:
    print(result[N-1][M-1] - 1)
else:
    print(-1)


# 7 4
# 0000
# 1110
# 1000
# 1000
# 0000
# 0111
# 0000
# answer: 10

 

✅  성공 코드 

from sys import stdin
from collections import deque

input = stdin.readline

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

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

def bfs(graph, start):
    queue = deque([start])
    visited = [[[0, 0] for _ in range(M)] for _ in range(N)]
    visited[0][0][0] = 1 # 시작점 방문 표시

    # directions
    directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]

    while queue:
        x, y, flag = queue.popleft()

        if x == N - 1 and y == M - 1:
            return visited[x][y][flag]

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < N and 0 <= ny < M:
                # 벽이 아니고 아직 방문하지 않은 경우
                if graph[nx][ny] == 0 and visited[nx][ny][flag] == 0:
                    visited[nx][ny][flag] = visited[x][y][flag] + 1
                    queue.append((nx, ny, flag))
                # 벽이고 아직 벽을 부수지 않은 경우
                elif graph[nx][ny] == 1 and flag == 0 and visited[nx][ny][1] == 0:
                    visited[nx][ny][1] = visited[x][y][0] + 1
                    queue.append((nx, ny, 1))
    # 도달할 수 없을 경우
    return -1

print(bfs(walls, (0, 0, 0)))


# 7 4
# 0000
# 1110
# 1000
# 1000
# 0000
# 0111
# 0000
# answer: 10