[Python]1216-백준-알고스팟

1. 문제 출처

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

1261번: 알고스팟

2. 풀이

BFS를 이용하지만 벽을 부수는 경우가 있기 때문에 데이크스트라 알고리즘도 같이 이용해야 한다.

벽부시는 것을 가중치로 두고 만약 벽을 부수지 않고 이동한다면, 가중치를 더해주지 않는 것이 필요하다.

다음과 같이 진행된다.

1. 상하좌우 중 범위를 나가지 않는 곳으로 이동

2. 해당 이동좌표에 벽이 있다면 전 가중치+1 을 해주고 append를 통해 큐의 끝에 넣어준다

3. 해당 이동좌표에 벽이 없다면 전 가중치를 넣어주고 appendleft를 통해 큐의 시작에 넣어준다.

from collections import deque

# 입력
m,n = map(int,input().split())

maze = []
graph = [[-1] * m for _ in range(n)]
dx = [0,0,-1,1]
dy = [-1,1,0,0]

for _ in range(n):
    maze.append(list(map(int,list(input()))))
    
# bfs 실시
q = deque([[0,0]])
graph[0][0] = 0
while q:
    x,y = q.popleft()
    for idx in range(4):
        xx = x + dx[idx]
        yy = y + dy[idx]
        # 만약 목표 좌표이면 반복문에서 나온다.
        if( xx==n-1) & (yy == m-1):
            graph[xx][yy] = graph[x][y]
            q.clear()
            break
        # 이동이 가능한 좌표이면
        if (0<=xx<n )& (0<=yy<m):
            # 방문히지 않은 좌표이면
            if graph[xx][yy] == -1:
                # 이동한 좌표에 벽이 있다면
                if maze[xx][yy] == 1:
                    # 이동하기전 총 가중치에 + 1을 해당 좌표에 저장
                    graph[xx][yy] = graph[x][y] + 1
                    # 큐에 추가
                    q.append([xx,yy])
                # 이동한 좌표에 벽이 없다면
                elif maze[xx][yy] == 0:
                    # 이동하기전 총 가중치를 해당 좌표에 저장
                    graph[xx][yy] = graph[x][y]
                    # 큐 시작부분에 저장
                    q.appendleft([xx,yy])
                    
print(graph[n-1][m-1])