[BOJ-14503] 로봇청소기2

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

14503번: 로봇 청소기

---

문제를 꼼꼼히 잘 읽는 습관을 들이자.

BFS 를 활용하고, 문제를 이해했다면, 푸는데 어려움이 없다.

그리고 문제의 예제2에서 왜 57이 나오는지 로직의 흐름을 알아야한다.

 

여기서 주의해야하는 것은

로봇청소기는 현재방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다는 규칙2번이다.

 

(2-a) 왼쪽방향에 아직 청소하지 않은 공간이 존재한다면

그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.

 

현재 큐에서 POP한 현재방향 d를 기준으로

현재방향 d의 왼쪽방향이 벽이아니고, 로봇이 아직 청소하지 않은 상태인지를 탐색해야한다.

그러기 위해서는 현재방향 d의 왼쪽방향이 어디인지를 고려해야한다.

 

현재방향이 0일때(북), 왼쪽방향은 서쪽(3) 이다.

현재방향이 1일때(동), 왼쪽방향은 북쪽(0) 이다.

현재방향이 2일때(남), 왼쪽방향은 동쪽(1) 이다.

현재방향이 3일때(서), 왼쪽방향은 남쪽(2) 이다.

---

(2-b) 왼쪽방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.

개인적으로 나는 이조건의 "그방향"이 무엇인지 헷갈렸다.

예제2에서 57이 나오도록 직접 그리면서 계산한결과, 그 방향은 "현재방향 d의 왼쪽방향"이다.

 

만일 현재방향 d가 0인경우, 현재방향의 왼쪽방향은 3(서쪽) 이다.

그런데 이미 청소를 한 상태거나, 벽이라면, 현재방향d를 0에서 3으로 바꾼다.

 

현재방향 d가 3인경우, 현재방향의 왼쪽방향은 2(남쪽)이다.

그런데 이미 청소를 한 상태거나 벽이라면, 현재방향 d를 3에서 2로 바꾼다.

 

현재방향 d가 2인경우, 현재방향의 왼쪽방향은 1(동쪽)이다.

그런데 이미 청소를 한 상태거나 벽이라면, 현재방향 d를 2에서 1로 바꾼다.

 

현재방향 d가 1인경우, 현재방향의 왼쪽방향은 0(북쪽)이다.

그런데 이미 청소를 한 상태거나 벽이라면, 현재방향 d를 1에서 0로 바꾼다.

 

즉, 기준방향은 동/서/남/북을 가리키므로 최대 4번을 회전할 수 있다.

최대 4번회전하다가, 현재방향을 기준으로한 왼쪽방향이 아직 청소하지 않은 상태인것을 발견하면

그 위치와 방향을 큐에 넣는다.

 

그리고 (2-a)와 (2-b)를 수행하면, (2-c)과정을 진입하지 못하도록

isStop 변수를 넣었다.

---

(2-c) 네 방향 모두 청소가 이미되었거나 벽인 경우에는, 바라보는 방향을 유지한채로 한칸 후진을 하고

2번으로 돌아간다.

 

(2-c)의 경우는 (2-b)에서 4번의 기준방향 회전을 했음에도 청소할 공간을 발견하지 못한경우에 해당된다.

그러면 후진이 가능한지 확인해야한다.

여기서 후진은, 현재방향 d의 반대방향이라고 보면된다.

 

현재방향이 0일때(북), 후진방향은 남쪽(2) 이다.

현재방향이 1일때(동), 후진방향은 서쪽(3) 이다.

현재방향이 2일때(남), 후진방향은 북쪽(0) 이다.

현재방향이 3일때(서), 후진방향은 동쪽(1) 이다.

 

현재 방향의 후진방향에 해당하는 공간이 0이라면 큐에 넣는다.

 

 

---

[코드]

import sys
from copy import deepcopy
from collections import deque

sys.setrecursionlimit(10**6)
input=sys.stdin.readline
q=deque()

N,M=0,0
MAP=None
visited=None

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

def isRange(y,x):
    global N,M
    if (y>=0 and y<N) and (x>=0 and x<M):
        return True
    return False

       
#d: 현재방향
#d=0(북)의 왼쪽방향 d_left=3(서)/ 후진:d_back=2(남)
#d=1(동)의 왼쪽방향 d_left=0(북)/ 후진:d_back=3(서)
#d=2(남)의 왼쪽방향 d_left=1(동)/ 후진:d_back=0(북)
#d=3(서)의 왼쪽방향 d_left=2(남)/ 후진:d_back=1(동) 방향은 d그대로 유지
def now_left_and_back(d):
    if d==0:#북
        return 3,2 #왼쪽방향, 후진방향
    elif d==1:#동
        return 0,3
    elif d==2:#남
        return 1,0
    #서
    return 2,1

def bfs():
    global N,M, MAP, visited
    
    while q:
        y,x,d=q.popleft()
        #현재방향을 복사하여, 2-a/b 과정의 탐색용으로 한다.
        d_copy=deepcopy(d)

        #방문했는지 확인
        if not visited[y][x]:
            visited[y][x]=True

        #2-a/b과정에서 왼쪽공간을 찾은 경우에는 2-c를 수행하지 못하도록함.
        isStop=False
        
        #(2-a/b과정). 현재방향을 기준으로 왼쪽방향에 청소할 수 있는지 탐색
        for _ in range(4): #최대회전수 4번
            #현재방향의 왼쪽방향과 후진방향
            d_left, d_back= now_left_and_back(d_copy)
            lefty, leftx= y+dy[d_left], x+dx[d_left]
            if (MAP[lefty][leftx]==0) and (not visited[lefty][leftx]):
                q.append((lefty, leftx, d_left))
                isStop=True
                break
            #현재방향의 왼쪽방향으로 기준방향으로 한다.
            d_copy=d_left
            
        #(2-a/b과정을 수행하지 못했다면)
        if not isStop:
            #2. 네방향이 이미 청소되거나 벽인경우
            #방향(d)를 그대로 유지한채 후진이 가능한지 확인
            _ , d_back=now_left_and_back(d)
            backy, backx= y+dy[d_back], x+dx[d_back]
            if (MAP[backy][backx]==0):
                q.append((backy, backx, d))

def main():
    global N,M, MAP, visited
    #N: 세로, M:가로
    N,M= map(int, input().strip().split())
    
    #초기 로봇청소기의 위치(r,c)와 바라보는 방향
    #(d=0) 북 / (d=1) 동 / (d=2) 남 / (d=3) 서
    r,c,d=map(int, input().strip().split())

    #장소맵그리기
    MAP=[]
    for y in range(N):
        MAP.append([*map(int, input().strip().split())])

    #방문리스트 만들기
    visited=[[False]*M for _ in range(N)]
    q.append((r,c,d))
    bfs() #bfs탐색
    
    #visited가 True인것 개수를 카운트
    ans=0
    for y in range(N):
        for x in range(M):
            if visited[y][x]==True:
                ans+=1
    print(ans)

if __name__=='__main__':
    main()