[백준] 14503 로봇 청소기

백준 14503번 로봇 청소기

구현 / 시뮬레이션

 

 

[문제]

 

구현 + bfs 느낌?

 

 

[과정]

 

기본적으로 bfs를 사용해서 로봇 청소기를 이동시켰음

현재 방향(d)가 0,1,2,3으로 들어오는데 각각 북,동,남,서 방향이므로 dx,dy 좌표를 해당 순서에 맞게 배치 함

방향변수 d를 갱신하고 계속 사용하기 위해 (cnt-1) % 4 로 계속 왼쪽방향으로 돌려주었음

 

※ 기본 로직

• 현재 위치에서 bfs 실행                                                        ---------------- 1
• 큐에 들어있는 좌표를 방문처리하고 이동횟수를 1증가 시켜줌         ---------------- 1
• 현재 좌표에서 북동남서 방향이 이동가능한지 비교             ---------------- 2
• 만약 이동 할 위치가 아직 방문한 적이 없고 벽이 아니라면 큐에 넣어주고 반복문 종료   ---------------- 2.1~2.2
• 만약 4면이 모두 이동 불가라면               ---------------- 2.3
• 뒤쪽 방향이 벽인 경우에는 함수 종료                 ---------------- 2.4
• 뒤쪽 방향이 벽이 아닌 경우에는 한칸 뒤로 이동시켜주고 큐에 해당 좌표를 넣어 줌           ---------------- 2.3

 

※ 생각할 부분 ※

1) 핵심 : 왼쪽으로 회전시키기

북,동,남,서의 방향대로 인덱스가 0,1,2,3이므로 왼쪽으로 회전하면 3->2->1->0->3->... 의 번호로 변경됨

즉 d(방향변수)를 -1하면서 상하좌우를 비교하면 됨

 

2) 만약 모든 면이 이동 불가능(벽 or 이미 방문된 좌표)하다면 뒤에가 벽이 아닐경우 뒤로 돌아가는 작업이 필요함

해당 부분은 d(방향변수)를 (cnt-2) % 4 로 큐에 넣어주면 됨    # 북-> 남   동->서  이렇게  2인덱스 차이만큼 반대이기 때문

또한 해당 좌표는 이미 방문처리되어있기 때문에 ans(청소한 칸수)를 증가시키지 않는 별도의 예외처리가 필요함

 

 

// 사실 문제의 알고리즘을 구현형식으로 모두 구현하지 않아도 그냥 0인경우를 모두 찾는 기본 bfs만을 돌려도 통과할 것 같은 문제였다.

그렇게하면 20분내로 풀 수 있었을 것 같지만 문제의도대로 시뮬레이션으로 풀어보니 1시간반이 걸렸다.

진짜 시간 단축좀 해야겠다;;

 

 

 

 

[소스코드]

 

# 14503 로봇 청소기
from collections import deque
import sys
input = sys.stdin.readline

def bfs(r,c,d):
    ans = 0
    visited = [[False]*m for _ in range(n)]
    q = deque()
    q.append((r,c))
        
    while q:
        x,y = q.popleft()
        if not visited[x][y]:
            ans+=1
        visited[x][y] = True   # 현재 위치 청소
        cnt = 0   # 네방향 이동 가능 여부
        for i in range(4):
            d = (d-1) % 4
            nx, ny = dx[d]+x, dy[d]+y
            if not visited[nx][ny] and arr[nx][ny] == 0:
                q.append((nx,ny))
                break
            else:
                cnt += 1
            # 네 방향 모두 청소되어 있는 경우
            if cnt == 4:
                # 뒤쪽 방향이 벽인 경우
                if arr[x+dx[(d-2)%4]][y+dy[(d-2)%4]] == 1:
                    return print(ans)
                q.append((x+dx[(d-2)%4],y+dy[(d-2)%4]))
    return print(ans)


n,m = map(int,input().split())
r,c,d = map(int, input().split())
arr = [list(map(int,input().split())) for _ in range(n)]
dx,dy = (-1,0,1,0), (0,1,0,-1)   # 북:0 동:1 남:2 서:3   cnt = (cnt-1) % 4

bfs(r,c,d)

 

---

 

[통과]