(Python) 백준 14503번 - 로봇 청소기

문제 링크: https://www.acmicpc.net/problem/14503

풀이

구현/시뮬레이션 문제로 풀이를 위해 딱히 복잡한 알고리즘이 필요하지 않다. 하지만 골드 문제이기에 조금 복잡한 구현을 거쳐야한다.

 

코드에서 가장 중요한 부분은 다음 이동 방향을 파악하는 것이다. 반시계 방향으로 청소해야할 부분이 있는지 체크해야한다고 했으므로, 북 -> 서 -> 남 -> 동 방향으로 체크해야한다. 이는 코드 상에서 0 -> 3 -> 2 -> 1인데, 여기에 +4를 더하고, 4로 나눈 나머지를 사용하여 마치 4 -> 3 -> 2 -> 1인 것처럼 체크될 수 있도록 하여서 로봇 청소기의 방향 전환을 쉽게 구현하였다.

위의 방향 전환 구현이 조금 고민이 되고 어려운 파트였으나, 나머지는 단순히 어려움 없이 문제에 표시된 대로 로봇 청소기가 행동하도록 구현하면 된다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
r, c, d = map(int, input().split())
places = [list(map(int, input().split())) for _ in range(n)]

visited = [[0 for _ in range(m)] for _ in range(n)]

answer = 0 # 청소한 칸의 수

def get_dir(d):
    if d == 0: # 북쪽
        dr = -1
        dc = 0
    elif d == 1: # 동쪽
        dr = 0
        dc = 1
    elif d == 2: # 남쪽
        dr = 1
        dc = 0
    else: # 서쪽
        dr = 0
        dc = -1
    return dr, dc

def check_dirty(d, r, c):
    for i in range(1, 5): # 반시계 방향으로 돌면서
        new_d = (d + 4 - i) % 4 # (4 -> 3 -> 2 -> 1)이 되도록 하기 위해 +4와 %4를 사용
        dr, dc = get_dir(new_d) # new_d의 값에 따라 움직일 방향 결정
        nr = r + dr
        nc = c + dc

        if nr < 0 or nr >= n or nc < 0 or nc >= m: # 다음 칸이 이동할 수 없는 곳이라면
            continue # 현재 방향은 스킵
        if visited[nr][nc] == 0 and places[nr][nc] == 0: # 다음 칸이 이동할 수 있고, 청소도 되지 않았다면
            return new_d # 이 방향으로 로봇 청소기가 진행하면 됨
    return None


while True:
    if visited[r][c] == 0 and places[r][c] == 0: # 현재 위치한 칸이 청소가 되어 있지 않다면
        answer += 1 # 청소한 칸의 수를 업데이트하고
        visited[r][c] = 1 # 청소를 진행했음을 표시

    new_d = check_dirty(d, r, c) # 현재 칸을 기준으로 주변 4칸 중 청소할 칸이 있는지 확인
    if new_d is not None: # 청소할 칸이 있는 경우
        d = new_d # 청소기가 그 뱡항으로 이동할 것임을 설정
        dr, dc = get_dir(d) # 설정된 방향으로
        r += dr # 이동
        c += dc # 이동

    else: # 모든 방향을 돌면서 체크했으나, 청소할 곳이 없는 경우
        dr, dc = get_dir(d) # 현재 방향의
        r -= dr # 반대로
        c -= dc # 이동

        if places[r][c] == 1: # 만약 현재 방향의 반대로 이동했으나, 벽을 마주친 경우에는
            break # 더 이상 로봇 청소기는 움직일 수 없음

print(answer)