[BOJ] 1261. 알고스팟(Python) / BFS

www.acmicpc.net/problem/1261

1261번: 알고스팟

이 문제는 어제 풀었던 미로만들기 문제

2021.03.25 - [Problem Solving/boj] - [BOJ] 2665. 미로만들기(Python) / BFS와 완전 같은 문제이다.

어제 풀었던 덕인지 30분 정도 소요했다.

 

• 사용 알고리즘 : BFS
• check 배열을 주어진 맵의 크기와 같게 만들고, 최댓값으로 초기화했다.
• 빈 공간일 때와 벽을 만났을 때 모두 이동 위치에 있는 값을 최솟값으로 갱신할 수 있을 때만 이동할 위치의 값을 갱신했다.
• 단, 빈 공간인 경우 기회를 사용하지 않고 그냥 이동 가능하므로 appendleft()로 큐의 헤드 부분으로 넣어 다음에 큐에서 값을 뽑을 때 바로 검사할 수 있도록 설계했다.
• 목적지에 도착했을 때, 해당 위치에 값을 리턴한다.

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline
from collections import deque

dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)

def bfs():
    check = [[float('inf') for _ in range(C)] for _ in range(R)]
    check[0][0] = 0
    
    Q = deque([(0, 0)])
    while Q:
        r, c = Q.popleft()
        if (r, c) == (R-1, C-1):        # 목적지 도착
            return check[R-1][C-1]
            
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            if not (0 <= nr < R and 0 <= nc < C):
                continue
            # 빈 공간일 때 벽 부순 횟수가 적게 걸린 값일 때만 갱신
            if A[nr][nc] == '0':
                if check[nr][nc] > check[r][c]:
                    check[nr][nc] = check[r][c]
                    Q.appendleft((nr, nc))      # 빈 공간이면 큐의 앞쪽으로 넣어줌
            
            # 벽 만났을 때 벽 부순 횟수가 적게 걸린 값일 때만 갱신
            else:
                if check[nr][nc] > check[r][c] + 1:
                    check[nr][nc] = check[r][c] + 1
                    Q.append((nr, nc))

# main
C, R = map(int, input().split())
A = [list(input().strip()) for _ in range(R)]
print(bfs())

---

• 시간 : 164ms / 메모리 : 126196kb
• 고찰 : 익숙해지면 비슷한 문제를 접할 때 풀이법이 빠르게 떠오른다. 알고리즘 문제를 많이 풀어봐야 하는 이유다.