[백준] 14503번: 로봇 청소기 (골드 5, 파이썬)

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

14503번: 로봇 청소기

 

아이디어

순서도에 적힌대로 구현하면 되는 문제였다.

 

해당 문제에는 로봇 청소기가 바라보는 방향 정보를 가지고있다. 

본문에는 아래와 같이 써져있다.

로봇 청소기가 바라보는 방향 d가 입력된다. d가 0인 경우 북쪽, 1인 경우 동쪽, 2인 경우 남쪽, 3인 경우 서쪽을 바라보고 있는 것이다.

 

그래서 우선 방향 이동 벡터는 0번째에 북쪽을 바라보고 직진하는 경우, 1번째에 동쪽을 바라보고 직진하는 경우, 2번째에 남쪽을 바라보고 직진하는 경우, 3번째에 서쪽을 바라보고 직진하는 경우로 구성하였다.

 

dv = [(-1, 0), (0,1), (1, 0), (0,-1)] # 방향 이동 벡터

 

이 방향 이동 벡터를 사용하는 경우는 두 가지이다.

1. 반시계 방향으로 회전 

2. 바라보는 방향을 그대로 두고 후진

 

반시계 방향으로 회전하는 경우는 (d + 3) % 4 로 회전한 방향을 구해준 후, 해당하는 방향 이동 벡터 값을 더해주면 된다.

        for _ in range(4): 
            d = (d + 3) % 4     # 반시계 방향으로 네 방향 검사
            nx = x + dv[d][0]
            ny = y + dv[d][1]

 

바라보는 방향을 그대로 두고 후진하는 경우는 방향 이동 벡터를 +가 아닌 -로 계산해주면 된다.

            tmp_x = x - dv[d][0]
            tmp_y = y - dv[d][1]

 

이 두 가지만 해결하니, 막힘 없이 풀 수 있었다.

 

전체 코드

from collections import deque

# 로봇 청소기가 바라보는 방향 d
# 0인 경우 북쪽 
# 1인 경우 동쪽 
# 2인 경우 남쪽 
# 3인 경우 서쪽

N, M = map(int, input().split())
r, c, d = map(int, input().split())
maps = [ [ int(x) for x in input().split()] for _ in range(N) ]

dv = [(-1, 0), (0,1), (1, 0), (0,-1)] # 방향 이동 벡터

def bfs(x, y, d):

    cnt = 1
    maps[x][y] = 2

    queue = deque()
    queue.append((x, y))

    while queue:
        x, y = queue.popleft()
        is_in = False

        for _ in range(4): 
            d = (d + 3) % 4     # 반시계 방향으로 네 방향 검사
            nx = x + dv[d][0]
            ny = y + dv[d][1]

            if 0 <= nx < N and 0 <= ny < M and maps[nx][ny] == 0:
                maps[nx][ny] = 2
                queue.append((nx,ny))
                cnt += 1
                is_in = True
                break


        if is_in == False: # 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
            # 후진
            tmp_x = x - dv[d][0]
            tmp_y = y - dv[d][1]
            
            # 벽이나 범위 내가 아니면 종료
            if tmp_x < 0 or tmp_x >= N or tmp_y < 0 or tmp_y >= M or maps[tmp_x][tmp_y] == 1:
                return cnt
            
            # 후진 가능하면 반복
            queue.append((tmp_x, tmp_y))
    return cnt

print(bfs(r, c, d))