[BOJ] 1726. 로봇(Python) / BFS

www.acmicpc.net/problem/1726

1726번: 로봇

 

BFS 최단거리 문제다.

처음에 문제 봤을 때 어떻게 풀어야할지 좀 막막했는데 여러 솔루션들을 보고 아이디어를 얻었고, 

특히, 뚱이가 코드를 보내줘서 완벽히 이해할 수 있었다.

내 스타일대로 다시 풀어봤다.

• 이 문제에서 포인트는 visited를 맵의 크기대로 그리되, 각 위치별로 4방향(동서남북) 정보를 담을 수 있도록 * 4 해주는 것!
• 큐에 위치와 방향, 그리고 cnt값을 담았다.
• 해당 정보를 visited에 표시하며 이동시켰다.
• while문 안에는 먼저 1, 2, 3칸 직진하는 명령을 수행하도록 했고,
  • 격자 밖으로 나가거나 벽 만나면 break한다.
  • 이미 방문한 곳이라면 continue, 방문하지 않은 곳이라면 새로 방문표시하며 이동한 정보를 큐에 담는다.
• 방향 바꾸는 것은 현 방향이 동, 서(0, 1)라면 남, 북(2, 3) 방향으로 전환하며 탐색하고,  현 방향이 남, 북(2, 3)이라면 동, 서(0, 1)로 바꾼다. 이는 마스킹해서 쉽게 전환할 수 있다.
  • 이미 방문한 곳이라면 continue, 그렇지 않다면 새로 방문 표시하며, 이동한 정보를 큐에 담는다. 
• 목표 위치와 방향에 도달했을 때, cnt값을 리턴한다.

 

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

---

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

# 동 서 남 북
dr = (0, 0, 1, -1)
dc = (1, -1, 0, 0)
change_dir = ((2, 3), (2, 3), (0, 1), (0, 1))

def bfs():
    visited = [[[0] * 4 for _ in range(C)] for _ in range(R)]
    visited[sr-1][sc-1][sd-1] = 1
    Q = deque([(sr-1, sc-1, sd-1, 0)])
    while Q:
        r, c, d, cnt = Q.popleft()
        if (r, c, d) == (gr-1, gc-1, gd-1):     # (목표위치와 방향)에 도착하면 cnt 리턴
            return cnt

        # 1, 2, 3칸 직진
        for dis in range(1, 4):
            nr = r + dr[d] * dis
            nc = c + dc[d] * dis
            nd = d
            # 맵 벗어나거나 벽 만나면 break
            if not (0 <= nr < R and 0 <= nc < C) or A[nr][nc]:
                break
            if visited[nr][nc][nd]:
                continue
            Q.append((nr, nc, nd, cnt+1))
            visited[nr][nc][nd] = 1

        # 방향 바꾸기
        for nd in change_dir[d]:
            if visited[r][c][nd]:
                continue
            Q.append((r, c, nd, cnt+1))
            visited[r][c][nd] = 1

# main
R, C = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(R)]
sr, sc, sd = map(int, input().split())
gr, gc, gd = map(int, input().split())

print(bfs())

---

• 시간 : 176ms / 메모리 : 126316KB
• 고찰 : 어렵지 않은 문제인데 처음에 아이디어가 떠오르지 않아 좀 헤맸다. 이젠 완벽하게 이해해서 내 힘으로 풀 수 있다! 상태관리를 해야하는 BFS 문제를 자유롭게 코드를 짤 수 있는 연습을 많이 해야겠다.