*문제 출처는 백준에 있습니다.
문제 제목: 로봇 청소기 / 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의 값으로 갱신이 됩니다.
'Coding Test > 백준-Python' 카테고리의 다른 글
| 백준 / 숨바꼭질 2 / 12851번 / Python (0) | 2025.03.24 |
|---|---|
| 백준 / 캠프가는 영식 / 1590번 / Python (0) | 2025.03.23 |
| 백준 / 다리 만들기 / 2146번 / Python (0) | 2025.03.20 |
| 백준 / 퇴사 2 / 15486번 / Python (0) | 2025.03.18 |
| 백준 / 안전 영역 / 2468번 / Python (0) | 2025.03.17 |