[백준 14503번 - 로봇청소기]-파이썬

solved.ac 난이도 :  GOLD5

백준  14503번- 파이썬 풀이

 

<문제>

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

14503번: 로봇 청소기

<풀이>-구현,시뮬레이션

이 문제의 핵심은 다음 두가지다.

• 방향이 d일때 왼쪽으로 회전한 뒤 방향은 (d+3) % 4가 된다.(북쪽 : 0, 동쪽:1 , 남쪽 = 2, 서쪽 = 3)
• 인접한 4방향을 탐색하면서 로봇청소기가 이동가능한 방향일시 바로 이동하고 탐색을 멈춘다.

우선 로봇청소기가 왼쪽으로 회전할때 X좌표와 Y좌표의 변화를 담을 dx,dy배열을 만든다. 이때 배열의 각 인덱스는 로봇청소기의 방향과 똑같이 설정한다.

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

	0	0
0	2,d = 0
	0	0

위 표를 예로 살펴보자. (1,1)의 위치에 로봇청소기가 있다고 하고 현재 바라보고 있는 방향은 0(북쪽)이라고 가정하자.

 

문제에서 왼쪽부터 회전한다 했으므로 로봇청소기가 바라보고 있는 방향의 서쪽부터 탐색한다.

 

북쪽을 바라보고 있는 경우 다음과 같은 순서로 회전하게 된다.

서쪽->남쪽->동쪽->북쪽

 

dx,dy배열에서 서쪽의 인덱스는 3이므로 배열의 인덱스를 3->2->1->0순으로 살펴보아야한다.

 

이때 서쪽 방향을 보면 0이므로 청소가 가능한 지역이다. 

 

그러면 d = (d+3)%4를 통해 d = 3(서쪽)으로 바꿔주고(핵심 1), 로봇청소기를 해당지역으로 옮긴다음 서쪽을 바라보고 있는 상태로 다시 인접방향을 탐색하기 시작한다.

	0	0
0->2 , d = 3	2,d = 0
	0	0

 

로봇청소기를 옮기는것은 처음 로봇청소기가 있던 r,c를 인접지역 nx,ny로 갱신함으로써 구현한다.

 

만약 로봇청소기가 방문한 지역이라면 visitied배열의 값은 1이고 아닌지역은 0이다.

 

만약 현재 탐색하고 있는 방향이 이동불가능한 지역인 경우 방향만 d = (d+3)%4를 통해 바꿔준다.

    unavail = 0
    #현재바라보고 있는 방향
    for _ in range(4): 
        nx = r+dx[(3+d)%4]
        ny = c+dy[(3+d)%4]
        #청소가 가능한 지역
        if 0<=nx<n and 0<=ny<m and graph[nx][ny]==0 and visitied[nx][ny]==0:
            d = (3+d)%4
            visitied[nx][ny] = 1
            r = nx
            c = ny
            count+=1
            unavail = 1
            break
        #청소가 불가능한 지역
        else:
            d = (3+d)%4

문제에서 4가지 방향 모두 이동이 불가능한 경우 후진한다고 하는 부분을 살펴보자

 

위 코드에서 for문을 돌면서 만약 이동가능한 지역이 하나라도 있다면 unavail = 1이 되지만, 만약 이동가능한 인접지역이 하나도 없다면 unavail은 변함없이 0 그대로 유지된다.

 

필자는 후진하는경우의 함수를 만들어 unavail = 0일때 후진하는 함수를 적용해 후진한 후의 위치를 반환하고 , 만약 해당위치가 벽이라면 코드를 종료하도록 구성했다.

#뒤로 후진하는 함수
def get_back(x,y,direction): #x,y : 현재위치, d :현재 바라보고 있는 방향
    if direction == 0 or direction == 1:
        nx = x+dx[direction+2]
        ny = y+dy[direction+2]
    if direction == 2 or direction == 3:
        nx = x+dx[direction-2]
        ny = y+dy[direction-2]
    return nx,ny
    

#후진한 곳의 위치가 벽이라면(1)종료, 그렇지 않다면 현재위치(r,c)를 후진한곳의 위치로 갱신
if unavail == 0:
    a,b = get_back(r,c,d)
    if graph[a][b] ==1:
       break
    else:
       r,c = a,b

728x90

<코드>-파이썬

#로봇청소기가 바로보고 있는 방향에 따라 회전방향 설정하기
#d:0 -> 북쪽 d:1->동쪽 d:2->남쪽 d:3->서쪽
#서쪽 : (0.-1),남쪽 : (1,0), 동쪽 :(0,1), 북쪽 : (-1,0)
dx = [-1,0,1,0]
dy = [0,1,0,-1]


#뒤로 후진하는 함수
def get_back(x,y,direction): #x,y : 현재위치, d :현재 바라보고 있는 방향
    if direction == 0 or direction == 1:
        nx = x+dx[direction+2]
        ny = y+dy[direction+2]
    if direction == 2 or direction == 3:
        nx = x+dx[direction-2]
        ny = y+dy[direction-2]
    return nx,ny

n,m = map(int,input().split())
r,c,d = map(int,input().split())
graph = []
for _ in range(n):
    graph.append(list(map(int,input().split())))

#청소여부 저장,0:청소X, 1: 청소 0
visitied = [[0]*m for _ in range(n)]
visitied[r][c] = 1
count = 1
while True:
    unavail = 0
    #현재바라보고 있는 방향
    for _ in range(4): 
        nx = r+dx[(3+d)%4]
        ny = c+dy[(3+d)%4]
        #청소가 가능한 지역
        if 0<=nx<n and 0<=ny<m and graph[nx][ny]==0 and visitied[nx][ny]==0:
            d = (3+d)%4
            visitied[nx][ny] = 1
            r = nx
            c = ny
            count+=1
            unavail = 1
            break
        #청소가 불가능한 지역
        else:
            d = (3+d)%4
    #만약 4가지 방향을 다 보았는데도 청소가능한 지역이 없는경우
    if unavail == 0:
        a,b = get_back(r,c,d)
        if graph[a][b] ==1:
            break
        else:
            r,c = a,b
            
print(count)

-마치며-

필자는 이문제를 처음 풀때 큐를 활용했다. 이동가능한 인접지역을 차례대로 큐에 방향과 함께 삽입하고 큐가 빌때까지 while문을 돌리는 방법을 사용했다. 하지만 이렇게 할 경우 후진한뒤의 현재위치를 후진한 지역으로 바꾸는데에 있어 어려움을 겪었다. 때문에 문제에서 인접가능한 지역이면 바로 이동을 한다는 것에 초점을 맞추어 이동가능한 지역이 있으면 탐색을 멈추고 새롭게 탐색을 시작한다는 부분에대해 많은 생각을 해봤다.