알고리즘

[시뮬레이션] - 14503 로봇 청소기

ghtis1798 2021. 9. 7. 21:37

7. 14503 로봇 청소기

image

7.1. 문제유형

  • 시뮬레이션

7.2. 풀이과정

  • 3가지를 정확히 구현해야 해결할 수 있었다.
  1. 좌표 이동을 기존 좌표계와 반대로 구현해야한다.
  2. 좌표 이동 시 방향 d가 현재 기준 왼쪽부터 탐색하도록 구현해야 한다.
  3. 방향 d에 대해 후진 위치를 정확히 지정해주어야 한다.
  • 1,2번까지는 제대로 구현했으나, 3번 제대로 지정하지 못해 오랜 시간이 소요되었다.

7.3. 소스코드

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

dx=[-1,0,1,0] #북,동,남,서
dy=[0,1,0,-1]

def DFS(x, y, d):
    global answer
    if graph[x][y]==0:
        graph[x][y]=2
        answer+=1

    for _ in range(4):
        idx=(d+3)%4
        nx,ny=x+dx[idx],y+dy[idx]
        if graph[nx][ny]==0:
            DFS(nx,ny,idx)
            return 0
        d=idx
    nd=(d+2)%4 # 후진 위치 지정
    nx,ny=x+dx[nd],y+dy[nd]
    if graph[nx][ny]==1:
        return 0
    DFS(nx,ny,d) # 방향을 유지한 채 후진

answer = 0
DFS(r, c, d)
print(answer)

7.4. 노트필기

image