백준 14503 로봇 청소기

문제 링크

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

한마디
말만 잘들으면 되는게 시뮬레이션인데, 나는 참 말을 안듣는다.

 

백준에 로봇 청소기 문제가 세 개인데 그 중 A형 기출문제인 문제이다.

DFS도 아닌, BFS도 아닌 문제의 디렉션만 따라가서 맞게 해주는 문제다. 

다만 주어지는 d의 경우 0, 1, 2, 3 이 각각 북 동 남 서 인데 막상 회전해야 하는 방향은 북 서 남 동 으로 반대인 점을 조심해야 한다. 

나는 복잡하게 생각하고 싶지 않아서 회전용 델타 리스트와 첫 바라보는 방향용 델타 리스트를 각각 만들어 주고 회전할 때는 앞 리스트를, 첫 회전 방향을 잡을 때 (ex; 북이면 서부터, 서쪽이면 남부터 등등) 와 후진을 할 때, 새로운 방향으로 갈 때에는 뒤 리스트를 써 주었다. 

 

 

#백준 14503 로봇청소기
dl = [(-1,0),(0,1),(1,0),(0,-1)] #북 동 남 서
rotate = [(0,-1),(1,0),(0,1),(-1,0)] # 서 남 동 북 0 = 0부터 1 = 3부터 2 = 2부터 3 = 1부터

def clean(x, y, d):
    global cnt
    if visited[x][y] == False:
        cnt+=1
        visited[x][y] = True #1번.현재 위치를 청소한다.
    if d == 0 or d == 2: #왼쪽으로 돌기(북 ->서, 남->동)
        rd = d
    else: #(서->남, 동->북)
        rd = 4-d
    shift = 0
    while shift<4: #2번. 현재위치에서 현재 방향을 기준으로
        #왼쪽방향부터 차례대로 탐색을 진행한다.(rotate 함수 이용)
        dx = rotate[rd][0] #도는 방향의 델타
        dy = rotate[rd][1]
        if 0<x+dx<N-1 and 0<y+dy<M-1 and room[x+dx][y+dy] == 0 and visited[x+dx][y+dy] == False: #왼쪽방향이 벽이 아니고
            clean(x+dx,y+dy,3-rd) #방문한적 없다면 그 방향으로 가서 1번부터 진행하기
            return
        else:
            shift+=1
            rd += 1 #2(b). 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
            if rd == 4:
                rd = 0
    nx = dl[d][0] #2(c) 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는
    ny = dl[d][1]
    if 0<x-nx<N-1 and 0<y-ny<M-1 and room[x-nx][y-ny] == 0:
        clean(x-nx, y-ny, d)#바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
        return
    else: #2(d) 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동멈추기
        return

N, M = map(int, input().split()) #세로크기와 가로크기가 주어진다
r, c, direction = map(int, input().split()) #로봇청소기의 좌표와 방향 d
visited = [[False for _ in range(M)] for _ in range(N)]
room = [list(map(int, input().split())) for _ in range(N)]
cnt = 0
clean(r,c,direction)
print(cnt)

 

11만의 적지 않은 메모리였지만 방 크기에 따라서 리스트가 두 개가 나오기 때문에 어쩔 수 없는 것 같고 결국 완전 탐색이 아니기 때문에 시간은 무난하게 통과할 수 있었다.