백준 / 14503번 로봇청소기 -bfs, 시뮬 / Python 파이썬

 

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

문제 제목: 로봇청소기 - bfs, 방향확인

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

 

문제 개요

• 로봇 청소기가 방을 청소하는 과정을 시뮬레이션한다.
• 로봇은 다음과 같은 규칙에 따라 움직인다:
  1. 현재 칸이 청소되지 않은 경우, 청소한다.
  2. 주변 4칸 중 청소되지 않은 빈 칸이 있으면, 반시계 방향으로 회전하면서 전진할 수 있는 칸을 찾고 이동한다.
  3. 청소되지 않은 칸이 없다면, 방향을 유지한 채 한 칸 후진한다.
  4. 후진할 수 없으면 작동을 멈춘다.

 

• 방향 처리
  • 방향은 북(0), 동(1), 남(2), 서(3) 으로 표현하며, directions 배열로 이동 좌표를 지정한다:
  • directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
  • 회전은 반시계 방향으로 처리하며, 왼쪽으로 회전할 때는 (d + 3) % 4 를 사용한다.

•  후진 처리
  • 현재 방향의 반대 방향은 (d + 2) % 4 로 구한다.
  • 후진 시에는 방향은 그대로 유지한 채, 뒤로 한 칸 이동한다.

---

나의 풀이

 

전체 로직 요약

1. 현재 칸을 청소 (청소 여부 확인 후 -1로 표시)
2. 왼쪽부터 반시계 방향으로 4방향 탐색:
    - 청소 안 된 빈 칸이 있으면 그쪽으로 이동, 방향 변경
3. 4방향 모두 청소되어 있다면 후진 시도:
    - 후진 가능한 경우 방향 유지하고 이동
    - 후진 불가(뒤에 벽)하면 종료

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

N, M = map(int, input().split())
sy, sx, d = map(int, input().split())

maps = [list(map(int, input().split())) for _ in range(N)]

# 북 동 남 서
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def bfs(sy, sx, d):
    queue = deque()
    queue.append((sy, sx, d))
    maps[sy][sx] = -1  # 청소 완료 표시
    count = 1

    while queue:
        y, x, d = queue.popleft()

        cleaned = False
        for i in range(4):
            nd = (d + 3 - i) % 4  # 반시계 회전 (왼쪽부터 확인)
            ny = y + directions[nd][0]
            nx = x + directions[nd][1]

            if 0 <= ny < N and 0 <= nx < M and maps[ny][nx] == 0:
                maps[ny][nx] = -1
                count += 1
                queue.append((ny, nx, nd))
                cleaned = True
                break

        if not cleaned:
            # 후진
            back_d = (d + 2) % 4
            by = y + directions[back_d][0]
            bx = x + directions[back_d][1]

            if 0 <= by < N and 0 <= bx < M and maps[by][bx] != 1:
                queue.append((by, bx, d))  # 방향 유지하고 후진
            else:
                break  # 후진도 못하면 끝

    return count

print(bfs(sy, sx, d))

 

클린코드........를쓰자

꼭 다시 풀어보기

처음에 로봇 방향을 전역으로 잡아버려서 틀림

 

 

24.04.02 재풀이

 

코드에서 방향 지정해주면 그냥 바꾸지말고 하라는대로 하자

반시계방향 (d + 3 - i) % 4

i = 0, d = 0, nd = 3 % 4 = 2

ny, nx 순서 바꿔적지말고 y는 무조건 열 x는 무조건 행 으로 간주해서 잘좀해보자

import sys
from collections import deque

input = sys.stdin.readline
N,M = map(int,input().split())

maps = []
sy,sx,d = map(int,input().split())
for i in range(N):
    maps.append(list(map(int,input().split())))
direction = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def bfs(sy,sx,d):
    global maps
    queue = deque([(sy,sx,d)])
    cnt = 1
    maps[sy][sx] = -1
    while queue:
        qy, qx, qd = queue.popleft()
        clean = False
        for i in range(4):
            nd = (qd +3 - i) %4
            ny, nx = qy + direction[nd][0], qx + direction[nd][1]
            if 0 <= ny < N and 0 <= nx < M:
                # 주변에 청소해야할 곳이 있다면
                if maps[ny][nx] == 0:
                    clean = True
                    queue.append((ny,nx,nd))
                    cnt += 1
                    maps[ny][nx] = -1
                    break
        if clean == False: # 벽이 있거나 청소를 못했으면 후진
            nd = (qd +2) % 4
            ny, nx = qy + direction[nd][0], qx + direction[nd][1]
            if 0 <= ny < N and 0 <= nx < M and maps[ny][nx] != 1:
                queue.append((ny,nx,qd)) # 방향은 유지한채 뒤로 간다
    return cnt

print(bfs(sy,sx,d))

---

※ 알아야 할 것

• robot_d와 같은 방향 정보를 전역변수로 두지 않고, 큐에 함께 저장해야 정확한 방향 관리가 가능하다.
• 매 시점마다 현재 위치와 방향을 함께 저장해서 큐에 넣고 관리한다.
• 회전 및 후진 시, 배열 범위를 벗어나지 않도록 좌표 체크를 철저히 해야 한다.
• 4방향 모두 확인했는데 이동할 곳이 없으면 반드시 후진 조건을 확인해야 한다.