로봇 청소기 골드 5 (백준, 구현)

import sys

input = sys.stdin.readline

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

# d => 0,3,2,1 순서로 돌아야한다.
dx = [-1,0,1,0]
dy = [0,1,0,-1]

for _ in range(n):
    graph.append(list(map(int,input().split())))

# 처음 시작하는 곳 방문 처리
visited[r][c] = 1
cnt = 1

while 1:
    flag = 0
    # 4방향 확인
    for _ in range(4):
        # 0,3,2,1 순서 만들어주기위한 식
        nx = r + dx[(d+3)%4]
        ny = c + dy[(d+3)%4]
        # 한번 돌았으면 그 방향으로 작업시작
        d = (d+3)%4
        if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0:
            if visited[nx][ny] == 0:
                visited[nx][ny] = 1
                cnt += 1
                r = nx
                c = ny
                #청소 한 방향이라도 했으면 다음으로 넘어감
                flag = 1
                break
    if flag == 0: # 4방향 모두 청소가 되어 있을 때,
        if graph[r-dx[d]][c-dy[d]] == 1: #후진했는데 벽
            print(cnt)
            break
        else:
            r,c = r-dx[d],c-dy[d]

 

일단 중요하다고 생각되는 부분은 %4를 이용하여 동서남북을 순서대로 확인하는 테크닉이라고 생각한다.

 

기존의 bfs,dfs 탐색의 경우 순서대로 값만을 대입하면 해결됐지만 해당 문제는 map의 사이즈와 동일한 메모리를 초기화하고 방향이 이미 설정된 값을 기준으로 탐색해야 하며 탐색 후의 테크닉 또한 준비되어야 한다.

 

문제를 차근히 보고 나눠서 분석하면 될 것이다.