[구현/백준] 14503번 : 로봇 청소기

- 문제 : https://www.acmicpc.net/problem/14503

 

문제 이해 

- 문제를 읽었을 때 탐색 문제라는 것은 파악을 했지만, 방향을 고려해야 하는 상황이 있어서 그 부분이 조금 어려웠다. 

- 청소기의 동작 방식은 다음과 같다 . 

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
   1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
   2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
   1. 반시계 방향으로 90도 회전한다.
   2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
   3. 1번으로 돌아간다

- 1번의 경우는 visit 행렬 값이 0인 곳인 경우 1로만 바꾸면 되고, 2번의 경우는 상하좌우에서 0인 칸이 없을 때 진행한다. 현재 위치의 방향에서 -1 할 수 있고, 돌아간 위치에서 상하좌우를 살펴서 빈 칸을 향해 움직인다. 만약 현재 방향에서 -1 칸 했는데 벽이라면 거기서 끝낸다. 3번은 상하좌우에서 visit 값이 0인 곳이 있으면 현재 방향에서 반시계 방향으로 90도 회전한 뒤 해당 방향을 앞쪽 칸 visit 값이 0인 경우에만 전진한다. 

 

- 반시계 방향 90도를 돌았을 때를 구현하기 위해 dx, dy도 그에 맞춰서 설정해줘야 한다. 

    - 0, 1, 2, 3 은 각각 북, 동, 남, 서 방향을 의미한다. 

    - 북(0)에서 반시계 90도를 돌면 서(3), 서(3)에서 반시계 90도를 돌면 남(2), 남(2)에서 반시계 90도를 돌면 동(1), 동(1)에서 반시계90도를 돌면 북(0)이다. 

    - 이는 현재 방향을 d라고 한다면 반시계 방향으로 90도 돌 경우 그 위치는 (d + 3) % 4를 의미한다. 

    - 그래서 dx, dy는 순서대로 북, 동, 남, 서 를 가리켜야 한다. 

 

- 작동 순서는 1, 2, 3으로 되어있지만 로직은 3, 1, 2 순서로 진행되어야 한다. 청소할 수 있는 칸을 확인한 다음, 청소할 수 있으면 하고, 청소할 수 있는 칸이 없다면 그때 뒤로 후진하고 벽을 만난다면 break를 해야한다. 

 

- 한 칸 전진한다는 의미는 x, y = x + dx[d], y + dy[d] 한다는 것이며, 한 칸 후진한다는 의미는 x, y = x - dx[d], y - dy[d] 한다는 의미이다. 

 

 

정답 풀이 

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
x, y, d = map(int,input().split())

matrix = []
visit = [[0] * m for _ in range(n)]

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

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

# 처음 시작하는 곳 방문 처리
visit[x][y] = 1
cnt = 1

while True:
    flag = False
    # 4방향 확인
    for _ in range(4):
        # 한번 돌았으면 그 방향으로 작업시작
        d = (d+3)%4
        
        # 현재 방향에서 반시계 방향 90도 회전
        nx, ny = x + dx[d], y + dy[d]
        
        # 상하좌우에서 접근할 수 있고, 방문하지 않은 위치 존재
        if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny] == 0:
            if not visit[nx][ny]:
                visit[nx][ny] = 1
                cnt += 1
                x, y = nx, ny
                #청소 한 방향이라도 했으면 다음으로 넘어감
                flag = True
                break
                
    if not flag: # 4방향 모두 청소가 되어 있을 때,
        if matrix[x - dx[d]][y - dy[d]] == 1: #후진했는데 벽
            print(cnt)
            break
        else:
            x, y = x - dx[d], y - dy[d]

 

참고 블로그 : https://resilient-923.tistory.com/164