[백준] 14503 로봇 청소기

https://www.acmicpc.net/problem/14503

14503번: 로봇 청소기

문제

로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 방은 �×�$N \times M$ 크기의 직사각형으로 나타낼 수 있으며, 1×1$1 \times 1$ 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 (�,�)$(r, c)$로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0,0)$(0, 0)$, 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 (�−1,�−1)$(N-1, M-1)$이다. 즉, 좌표 (�,�)$(r, c)$는 북쪽에서 (�+1)$(r+1)$번째에 있는 줄의 서쪽에서 (�+1)$(c+1)$번째 칸을 가리킨다. 처음에 빈 칸은 전부 청소되지 않은 상태이다.

로봇 청소기는 다음과 같이 작동한다.

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

입력

첫째 줄에 방의 크기 �$N$과 �$M$이 입력된다. (3≤�,�≤50)$(3 \le N, M \le 50)$  둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 (�,�)$(r, c)$와 처음에 로봇 청소기가 바라보는 방향 �$d$가 입력된다. �$d$가 0$0$인 경우 북쪽, 1$1$인 경우 동쪽, 2$2$인 경우 남쪽, 3$3$인 경우 서쪽을 바라보고 있는 것이다.

셋째 줄부터 �$N$개의 줄에 각 장소의 상태를 나타내는 �×�$N \times M$개의 값이 한 줄에 �$M$개씩 입력된다. �$i$번째 줄의 �$j$번째 값은 칸 (�,�)$(i, j)$의 상태를 나타내며, 이 값이 0$0$인 경우 (�,�)$(i, j)$가 청소되지 않은 빈 칸이고, 1$1$인 경우 (�,�)$(i, j)$에 벽이 있는 것이다. 방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다. 로봇 청소기가 있는 칸은 항상 빈 칸이다.

출력

로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.

예제 입력 1 복사

3 3
1 1 0
1 1 1
1 0 1
1 1 1

예제 출력 1 복사

1

예제 입력 2 복사

11 10
7 4 0
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 1 1 1 0 1
1 0 0 1 1 0 0 0 0 1
1 0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

예제 출력 2 복사

57

 

딱 이문제 보자마자 느낀건

내가 이코테에서 구현 공부하다가

짜증나서 말았던 문제와 매우 유사하단걸 느꼈다

삼전이 딱 저런 빡구현 좋아하는 것 같다

부끄럽지만 푸는데 한시간정도 걸렸다

그래도 .. 혼자 풀었다는게 좀 다행이다

import sys
def turn_left():
    global direction
    direction -=1
    if direction == -1:
        direction = 3

N,M = map(int,sys.stdin.readline().split())
x,y,direction = map(int,sys.stdin.readline().split())
graph = []
dx = [-1,0,1,0]
dy = [0,1,0,-1]

# 0,1,2,3 -> 북,동,남,서
for i in range(N):
    graph.append(list(map(int,sys.stdin.readline().split())))
count = 0

breaknumber = 0
while breaknumber == 0:
    flag = 0
    if graph[x][y] == 0:
        count +=1
        graph[x][y] = 2 # 1번 조건 . 현재 칸 청소
    for i in range(4): # 이제 2,3번 조건 turn around
        turn_left()
        nx = x + dx[direction]
        ny = y + dy[direction]
        if nx < 0 or ny < 0 or nx >= N or ny >=M:
            continue
        if graph[nx][ny] == 0:
            count +=1
            flag = 1 # 3번 조건
            graph[nx][ny] = 2 # 청소 완
            x,y = nx,ny
            break # for // break
       
    if flag == 0: # 만약 청소되지 않은 빈칸이 없다?
        direction2 = direction
        nx = x + dx[(direction2 + 2) % 4]
        ny = y + dy[(direction2 + 2) % 4] # 후진으로 이동
        if nx < 0 or ny < 0 or nx >=N or ny >=M or graph[nx][ny] == 1:
            breaknumber = 1 # 여기서 작동 중단
        x,y = nx,ny
print(count)

 

저렇게 주석을 달고 풀어야 구현 조건 하나하나 안 놓칠 수 있는 것 같다

확실한건 지금 위치를 갱신해줘야 한다는 것과

1이 그냥 장애물이 아니라 "벽"으로 인식한다는 문제의 조건이 중요했다

예전에 해설에서 turn_left 함수를 쓰면 편한걸 보고 이렇게 풀었다

 

정말 세세하게 문제를 읽고 코드로 옮기는 것이 중요한 것 같습니다

 

금융권 코테는 빡구현이 많이나오니까 구현 연습 열심히 할 것 ! 파이팅..