14503번 - 로봇 청소기

 

문제

14503번: 로봇 청소기 (acmicpc.net)

14503번: 로봇 청소기

풀이 1

 재귀함수를 이용한 기본적인 구현문제이다. DFS도, BFS도 아니고 구현 항목을 따라 작성하면 된다. 재밌는 문제라 따로 기록해둔다.

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
r,c,d = map(int,input().split())
board = []
for _ in range(n):
    board.append(list(map(int, input().split())))

# 북 동 남 서
dRow = [-1,0,1,0]
dCol = [0,1,0,-1]
visited = set()


def rotate_ccw_90(face):
    return face-1 if face > 0 else 3


def robot(row,col,face):
    visited.add((row,col))
    board[row][col] = 3
    for _ in range(4):
        face = rotate_ccw_90(face)
        nRow,nCol = row+dRow[face],col+dCol[face]
        if board[nRow][nCol] != 1 and not (nRow,nCol) in visited:
            robot(nRow,nCol,face)
            break
    else:
        backward = tuple(map(lambda x : x*-1, (dRow[face],dCol[face])))
        nRow,nCol = row+backward[0],col+backward[1]
        if board[nRow][nCol] != 1:
            robot(nRow,nCol,face)

robot(r,c,d)

print(len(visited))

풀이 2

청소기의 이동을 잘 구현하면 되는 간단한 문제이다.

N,M = map(int,input().split())
r,c,d = map(int,input().split())
board = []
for _ in range(N):
    board.append(list(map(int,input().split())))

# 북 동 남 서
dRow = [-1,0,1,0]
dCol = [0,1,0,-1]

answer = 0
visited = [[0]*M for _ in range(N)]
while True:
    # 청소
    if visited[r][c] == 0:
        answer += 1
        visited[r][c] = 1
    # 왼쪽 검사
    for _ in range(4):
        d = (d+3)%4
        nr,nc = r+dRow[d],c+dCol[d]
        if 0 <= nr < N and 0 <= nc < M and board[nr][nc] == 0 and visited[nr][nc] == 0:
            r,c = nr,nc
            break
    # 인접 칸들이 모두 청소했거나, 벽인 칸이라면
    else:
        nr,nc = r-dRow[d],c-dCol[d]
        if 0 <= nr < N and 0 <= nc < M and board[nr][nc] == 0:
            r, c = nr, nc
        else:
            break

print(answer)