[Python] 삼성 sw 역량 테스트 기출 - 로봇 청소기

www.acmicpc.net/problem/14503

14503번: 로봇 청소기

[ 알고리즘 ]

BFS,구현

 

[문제 접근]

이 문제는 방향에 대한 규칙만 찾으면 해결할 수 있는 문제이다

 

동,서,남,북을 편하게 오른쪽,왼쪽,아래쪽,위쪽이라고 했을 때,

 

- 문제에 주어진 방향

0: 위쪽

1: 오른쪽

2: 아래쪽

3: 왼쪽

 

< 고려해야할 경우>

 

1. 가는 방향을 기준으로 무조건 왼쪽으로 회전임을 주의

 

- 위쪽을 바라보고 있는 경우 : 왼쪽으로 이동

- 아래쪽을 바라보고 있는 경우 : 오른쪽으로 이동

- 오른쪽을 바라보고 있는 경우 : 위쪽으로 이동

- 왼쪽을 바라보고 있는 경우 : 아래쪽으로 이동

 

2. 후진 할때 ( 바라보고 있는 방향이 바뀌면 안됨)

 

- 위쪽을 바라보고 있는 경우 : 아래쪽으로 이동

- 아래쪽을 바라보고 있는 경우 : 위쪽으로 이동

- 오른쪽을 바라보고 있는 경우 : 왼쪽으로 이동

- 왼쪽을 바라보고 있는 경우 : 오른쪽 이동

 

벽이 있는 부분과 이미 청소된 부분을 구분하여 ( 예를들면 청소된 부분은 2로 채워넣기 )

처음에 시작 점만 잘 잡으면 다른 방향으로 갈때는 조건만 다르고 반복이므로 집중해서 방향을 잘 고려해주면 된다.

 

[코드]

시간 : 92ms

from collections import deque
import sys

N,M=map(int,sys.stdin.readline().strip().split())
a,b,di=map(int,sys.stdin.readline().strip().split())
graph=[]

for _ in range(N):
    graph.append(list(map(int,sys.stdin.readline().strip().split())))

cnt=0

que=deque()
que.append((a,b,di)) # 초기값 설정

while que:
    x,y,d=que.popleft()

    if graph[x][y]==0:
        graph[x][y]=2 # 청소 완료
        cnt+=1

    if d==0: # 위쪽 바라보고 있음
        if graph[x][y-1]==0: # 청소할 수 있음
            que.append((x,y-1,3)) # 왼쪽을 바라보는 중
        else: # 청소 못함
            if graph[x+1][y]==0: # 아래
                que.append((x+1,y,2))
                continue
            elif graph[x][y+1]==0: # 오른쪽
                que.append((x,y+1,1))
                continue
            elif graph[x-1][y]==0: # 위쪽
                que.append((x-1,y,0))
                continue
            else: #네 방향 모두 안됨
                if graph[x+1][y]==1: # 후진 했는데 벽임
                    break
                else: #벽 아님
                    que.append((x+1,y,0))
                    continue

    elif d==1: # 오른쪽 바라보고 있음
        if graph[x-1][y]==0: # 청소할 수 있음
            que.append((x-1,y,0)) # 위쪽 바라보는 중
        else: # 청소 못함
            if graph[x][y-1]==0: # 왼쪽
                que.append((x,y-1,3))
                continue
            elif graph[x+1][y]==0: # 아래
                que.append((x+1,y,2))
                continue
            elif graph[x][y+1]==0: # 오른쪽
                que.append((x,y+1,1))
                continue
            else: #네 방향 모두 안됨
                if graph[x][y-1]==1: # 후진 했는데 벽임
                    break
                else: #벽 아님
                    que.append((x,y-1,1))
                    continue

    elif d==2: # 아래쪽 바라보고 있음
        if graph[x][y+1]==0: # 청소할 수 있음
            que.append((x,y+1,1)) # 오른쪽 바라보는 중
        else: # 청소 못함
            if graph[x-1][y]==0: # 위
                que.append((x-1,y,0))
                continue
            elif graph[x][y-1]==0: # 왼쪽
                que.append((x,y-1,3))
                continue
            elif graph[x+1][y]==0: # 아래
                que.append((x+1,y,2))
                continue
            else: #네 방향 모두 안됨
                if graph[x-1][y]==1: # 후진 했는데 벽임
                    break
                else: #벽 아님
                    que.append((x-1,y,2))
                    continue

    elif d==3: # 왼쪽 바라보고 있음
        if graph[x+1][y]==0: # 청소할 수 있음
            que.append((x+1,y,2)) # 아래쪽 바라보는 중
        else: # 청소 못함
            if graph[x][y+1]==0: # 오른
                que.append((x,y+1,1))
                continue
            elif graph[x-1][y]==0: # 위
                que.append((x-1,y,0))
                continue
            elif graph[x][y-1]==0: # 왼쪽
                que.append((x,y-1,3))
                continue
            else: #네 방향 모두 안됨
                if graph[x][y+1]==1: # 후진 했는데 벽임
                    break
                else: #벽 아님
                    que.append((x,y+1,3))
                    continue

print(cnt)