[백준14503] 로봇 청소기

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

 

문제 해결 방법

이 문제는 문제 설명에 올라와있는대로 그대로 풀면 된다. 

 

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

 

다만 문제는 반시계 방향으로 90도씩 회전을 해야한다는 것이고, 

현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 발견되는 즉시!! 반시계 방향으로 90도 회전해야한다. 

 

코드 구현

 

정답 코드 

 

import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())
startY, startX, dir = map(int, input().split())
mapp = []
for i in range(n):
    mapp.append(list(map(int, input().split())))

dx=[0, -1, 0, 1] # 북 서 남 동
dy=[-1, 0, 1, 0] # 북쪽을 y, x 기준 1, 0으로 표기해서 틀렸음 ....... 정신차려!! 

def solutions(x, y, dir):
    cnt = 0 # 청소하는 칸의 개수 
    while 1:
        # 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
        if mapp[y][x] == 0:
            mapp[y][x]=9
            cnt+=1

        check = 0 # 주변 4칸이 모두 청소된 칸인지 확인용 1은 청소필요, 1은 청소 불필요 
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
        
            if mapp[ny][nx]==0:
                #청소 필요한 칸 발견
                check =1
                break
            
        if check == 1:
            # 반시계 방향으로 90도 회전
            dir=dir+1
            if dir==4:
                dir = 0
            sx=x+dx[dir]
            sy=y+dy[dir]
            
            if mapp[sy][sx]==0:
                # 전진함 
                x = sx
                y = sy
        
        # 청소가 필요 없는 경우 
        if check ==0:
            nny = y-dy[dir]
            nnx = x-dx[dir]
            
            if mapp[nny][nnx]==1:
                return cnt
            else:
                x=nnx
                y=nny

if dir ==1:
    dir = 3
elif dir ==2:
    dir =2
elif dir == 3:
    dir = 1
print(solutions(startX, startY, dir))

 

 

시간/공간 복잡도

시뮬레이션 문제라 고려하지 않았다. 

 

어려웠던 점

• 반시계 반향으로 회전하려면, 문제에서 제시한 방향 기준으로 델타 x, y의 배열을 미리 선언할 때 조심해야 한다. 
• 우측 상단 방향이 행, 열 값이 증가하는 상황이라면  북쪽 방향으로 가는것이 (1, 0)이겠지만 해당 문제의 경우, 우측 하단으로 가야 행, 열이 값이 증가하는 상황이다. 이런 경우 북쪽으로 가는 것은 (-1, 0)이다.

 

알게된 점

• 좌표 문제의 경우, 쪽이 행과 열을 증가시키는 쪽인지 잘 확인하고 이를 고려하여 문제를 풀어야한다. 
• 델타 x, y좌표 배열을 선언할 때도, 문제에서 관련 조건이나 방법을 제시하는지 잘 확인하여 선언해야 한다.