로봇 청소기 - 백준 #14503, 골드5, 구현/시뮬레이션

문제 링크

14503번: 로봇 청소기

풀이

# 입력값 받기
n, m = map(int, input().split())
r, c, d = map(int, input().split())
room = [list(map(int, input().split())) for _ in range(n)]

# 북, 동, 남, 서 방향 이동 좌표
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 현재 위치 청소
def clean(x, y):
    room[x][y] = 2

# 현재 위치에서 왼쪽 방향으로 회전한 방향 반환
def turn_left(d):
    return (d + 3) % 4

# 후진할 위치 반환
def back(x, y, d):
    return x - dx[d], y - dy[d]

# 현재 위치에서 탐색 시작
def dfs(x, y, d):
    # 현재 위치 청소
    clean(x, y)
    # 네 방향 모두 확인
    for _ in range(4):
        # 현재 방향에서 왼쪽 방향으로 회전
        nd = turn_left(d)
        # 다음 이동할 위치
        nx, ny = x + dx[nd], y + dy[nd]
        # 이동할 위치가 청소하지 않은 곳이면 이동하고 dfs 실행
        if room[nx][ny] == 0:
            dfs(nx, ny, nd)
            return
        # 이동할 위치가 청소한 곳이거나 벽이면 회전만 하고 다시 반복
        else:
            d = nd
    # 네 방향 모두 청소가 된 경우 후진하고 다시 실행
    bx, by = back(x, y, d)
    if room[bx][by] != 1:
        dfs(bx, by, d)

# 로봇 청소기 이동 시작
dfs(r, c, d)

# 청소한 구역 수 출력
count = 0
for i in range(n):
    for j in range(m):
        if room[i][j] == 2:
            count += 1
print(count)