[python] 백준 14503번: 로봇 청소기

문제

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

14503번: 로봇 청소기

분류

구현과 시뮬레이션

아이디어

설명대로 구현하되, DFS 모델에서 백트래킹이 없다고 보면된다. 다음 경우의 수를 찾으면 바로 break 걸어서 다른 경우의 수를 큐에 추가하지 않도록 해야한다. 문제를 꼼꼼히 읽지 않아 후진의 경우 를 코드로 구현하지않아서 이거 왜안돼?? 만 외친 채 40분정도를 날린 기분이다. 구현문제는 기본적으로 문제를 자아아알 읽는것이 정답의 길이다.

 

방향전환과 진행에 관해서는 예전에 기록한 방법을 이용했다.

choichumji.tistory.com/76?category=884672

[python] 진행 방향 시계,반시계 방향 꺾기 돌리기

반성

적혀있는대로 구현하면 되는 문제지만 나는 어리석게도 BFS,DFS 에서의 선택의 고민을 하다보니 오히려 시간을 다른 곳에 뺏겨버렸다.
사실 그럴필요는 없었다.

보드판 내의 청소구역은 count 로 채워나갈때 count 를 1부터 채워나가서 벽의 조건인 1 과 청소의 시작이 1 로 동일해서, 청소구역을 벽으로 인식하게 되서 후퇴를 못하는 케이스 때문에 20% 쯤에서 오답처리가 2번 발생했다. 알고리즘이 맞다고 해도 이런 디테일을 놓치면 틀리게 됨을 다시 느끼게 되었음.

코드

from sys import stdin
from collections import deque

N, M = map(int, stdin.readline().split())
r, c, d = map(int, stdin.readline().split())
board = [list(map(int, stdin.readline().split())) for _ in range(N)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 0 북 1 동 2 남 3 서 (절대)
q = deque()
q.append((r, c, d, 2))  # r c d count청소
ans = 0
while q:
    x, y, dir, count = q.popleft()
    next_d = dir
    flag = False
    if board[x][y] == 0:
        board[x][y] = count
    for _ in range(4):
        next_d = (next_d-1) % 4
        nx = x + dx[next_d]
        ny = y + dy[next_d]
        if board[nx][ny] == 0:
            q.append((nx, ny, next_d, count + 1))
            flag = True
            break

    if not flag:
        backward_dir = (dir - 2) % 4
        bx = x + dx[backward_dir]
        by = y + dy[backward_dir]

        if board[bx][by] != 1:
            q.append((bx, by, dir, count))

    ans = count -1

print(ans)