백준 / 로봇 청소기 / 14503번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 로봇 청소기 / 14503번 (골드 5단계)

문제 사이트: https://www.acmicpc.net/problem/14503

 

문제 설명

---

나의 풀이

from collections import deque


# d가 0인 경우 북쪽, 1인 경우 동쪽, 2인 경우 남쪽, 3인 경우 서쪽을 바라 본다
machine_move = {0: (-1, 0), 1: (0, 1), 2: (1, 0), 3: (0, -1)}
search = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 상 하 좌 우


def room_result(n, m, r, c, d, room):
    answer = 1 # 결과 값

    cleaner = [[False] * m for _ in range(n)]  # 청소 확인

    dq = deque([(r, c, d)])  # deque
    cleaner[r][c] = True  # 처음 위치는 무조건 청소한다. 1법칙

    while dq:  # 로봇 시작
        iy, ix, direction = dq.popleft()  # 방향
        check = False  # 청소해야할 곳이 생기면 True가 된다

        # 현재 칸의 주변 4칸 중 청소 탐색
        for ny, nx in search:
            y = iy + ny
            x = ix + nx
            # 벽을 확인
            if 0 < y < n - 1 and 0 < x < m - 1 and room[y][x] != 1:
                # 청소를 해야할 구역이 있다면
                if not cleaner[y][x] and room[y][x] == 0:
                    check = True

        # 청소를 해야할 구역이 있다면
        if check:
            for _ in range(4):
                # 반시계 방향 90도 회전
                direction = (direction - 1) % 4
                ny, nx = machine_move[direction]  # 보는 방향
                y = iy + ny
                x = ix + nx
                if 0 < y < n - 1 and 0 < x < m - 1 and not cleaner[y][x] and room[y][x] != 1:
                    dq.append((y, x, direction))  # 현재 위치와 방향을 저장함
                    answer += 1  # 값을 갱신
                    break  # 종료
        # 청소를 해야할 구역이 없다면 뒤로 가야함
        else:
            # 반대 방향 전환
            direction ^= 2

            ny, nx = machine_move[direction]  # 보는 방향
            y = iy + ny
            x = ix + nx
            if room[y][x] != 1:
                if not cleaner[y][x]:
                    cleaner[y][x] = True
                    answer += 1
                dq.append((y, x, direction))
            else:
                return answer


def main():
    n, m = map(int, input().split())  # 방 크기

    r, c, d = map(int, input().split())  # 좌표, 방향

    room = [list(map(int, input().split())) for _ in range(n)]  # 방 크기

    print(room_result(n, m, r, c, d, room))


main()

로직은 맞지만 뒤로가는 부분에서 반대 방향을 입력해서 넣어주면 후진한 다음에도 반대 방향으로 후진을하면 무한 루프에 빠질 수 있게 됩니다! 그걸 방지한 아래의 코드입니다.

from collections import deque


# d가 0인 경우 북쪽, 1인 경우 동쪽, 2인 경우 남쪽, 3인 경우 서쪽을 바라 본다
machine_move = {0: (-1, 0), 1: (0, 1), 2: (1, 0), 3: (0, -1)}
search = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 상 하 좌 우


def room_result(n, m, r, c, d, room):
    answer = 1 # 결과 값

    cleaner = [[False] * m for _ in range(n)]  # 청소 확인

    dq = deque([(r, c, d)])  # deque
    cleaner[r][c] = True  # 처음 위치는 무조건 청소한다. 1법칙

    while dq:
        iy, ix, direction = dq.popleft()  # 현재 위치와 방향을 가져옴
        check = False  # 주변에 청소할 구역이 있는지 확인할 플래그

        # 현재 칸의 주변 4칸 중 청소되지 않은 곳이 있는지 탐색
        for ny, nx in search:
            y = iy + ny
            x = ix + nx
            if 0 <= y < n and 0 <= x < m and room[y][x] == 0 and not cleaner[y][x]:
                check = True  # 청소할 구역이 있음
                break  # 더 이상 탐색할 필요 없음

        if check:
            # 주변에 청소할 곳이 있으면 반시계 방향으로 회전하며 한 칸씩 탐색
            for _ in range(4):
                direction = (direction - 1) % 4  # 반시계 방향 90도 회전
                ny, nx = machine_move[direction]
                y = iy + ny
                x = ix + nx
                if 0 <= y < n and 0 <= x < m and room[y][x] == 0 and not cleaner[y][x]:
                    cleaner[y][x] = True  # 청소 처리
                    answer += 1  # 청소한 칸 수 증가
                    dq.append((y, x, direction))  # 새로운 위치와 방향 저장
                    break  # 다음 단계로 넘어감
        else:
            # 주변에 청소할 곳이 없다면, 후진 시도
            back_dir = (direction + 2) % 4  # 현재 방향의 반대 방향 계산
            ny, nx = machine_move[back_dir]
            y = iy + ny
            x = ix + nx
            if 0 <= y < n and 0 <= x < m and room[y][x] == 0:
                dq.append((y, x, direction))  # 후진은 방향 유지
            else:
                return answer  # 후진 불가능(벽) → 작동 종료


def main():
    n, m = map(int, input().split())  # 방 크기

    r, c, d = map(int, input().split())  # 좌표, 방향

    room = [list(map(int, input().split())) for _ in range(n)]  # 방 크기

    print(room_result(n, m, r, c, d, room))


main()

---

※ 알아야 할 것

direction = (direction - 1) % 4  # 반시계 방향 90도 회전

이 부분에서 반시계 방향으로 90도 회전을 하게 되면 모듈러 연산을 통해 음수가 나와도 3의 값으로 갱신이 됩니다.