백준 14503 문제 풀이

🐒 로봇 청소기

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

✍ 나의 풀이

import sys

input = sys.stdin.readline


N, M = map(int, input().split())
r,c,d = map(int, input().split())

matrix = []
for _ in range(N):
    matrix.append(list(map(int,input().split())))

dx = [-1,0,1,0]
dy = [0,1,0,-1]

count = 1
x = r
y = c

while True:
    foundway = False
    matrix[x][y] = 2

    for _ in range(4):
        d = (d+3)%4
        nx = x + dx[d]
        ny = y + dy[d]

        if 0 < nx < N and 0 < ny < M:
            if matrix[nx][ny] == 0:
                x = nx
                y = ny
                foundway = True
                count += 1
                break
        
    if not foundway:
        nx = x + dx[(d+2)%4]
        ny = y + dy[(d+2)%4]
        if matrix[nx][ny] == 1:
            print(count)
            exit()
        else:
            x = nx
            y = ny

어떤식으로 풀어야할지 감은 오는데 직접 구현하기 어려워서 힘든 문제였다.

그래도 새로운 유형을 경험할 수 있어서 좋은 문제였다.

---

🧠 문제 이해

로봇청소기는 다음과 같이 동작한다.

1. 현재 위치를 청소한다.
2. 청소기가 왼쪽(반시계)으로 회전한다. 앞이 더러운 타일이면 앞으로 전진하고 1번으로 돌아한다. 깨끗한 타일이거나 벽이면 2번을 다시 실행한다.
3. 2번을 네번 실행했는데도 더러운 타일을 찾지 못했으면 후진 하고 1번으로 돌아간다. 후진 하려는 곳에 벽이 있으면 프로그램을 종료한다.

청소한 타일의 갯수를 출력한다.

---

처음에는 인접행렬을 만들어서 BFS로 탐색해야겠다 라고 생각했는데
막상 코드를 짜다보니 다른 문제처럼 인접한 여러 타일을 한번에 탐색하는게 아니라 한번에 한곳만 탐색하더라,
그래서 BFS로 탐색하는 코드는 없앴다.

헷갈렸던 부분은
처음에 방향정보 d 가 주어지는데, 0이면 북, 1이면 동, 2면 남, 3이면 서쪽을 가리키는 것이다.

예로 d=0 이면 회전을 할때 왼쪽으로 회전하므로 북에서 서쪽을 향하게 되고, d=3 이 된다. 왼쪽으로 회전하면 서에서 남을 가리키고 d=2가 된다.

나는 d의 변화를 어떻게 구현해야할지 몰라서 검색을 해보았는데

로 나타내면 왼쪽으로 회전함에 따라 d가 변하는것을 구현할 수 있다.
d = 3이라면 6을 4로 나눈 나머지가 2이므로 d = 2이다.

청소기를 왼쪽으로 회전시키면서 앞의 타일을 탐색하는 코드를 다음과 같이 작성했다.

dx = [-1,0,1,0]
dy = [0,1,0,-1]
 #d가 0이면 북쪽 (-1,0), 1이면 동쪽 (0,1)
 	# 2면 남쪽 (1,0), 3이면 서쪽(0,-1)

for _ in range(4):
        d = (d+3)%4
        nx = x + dx[d]
        ny = y + dy[d]

        if 0 < nx < N and 0 < ny < M: # 인덱스 초과를 막는 탐색범위 제한
            if matrix[nx][ny] == 0: # 더러운 타일이면
                # 청소기 nx ny칸으로 전진
                x = nx 
                y = ny
                foundway = True
                count += 1	# 청소한 타일 갯수 추가
                break

그리고 왼쪽으로 회전하는 식을 이용해서
후진하는 식을 만들면

이다.

---

코드

import sys

input = sys.stdin.readline


N, M = map(int, input().split())
r,c,d = map(int, input().split())

matrix = []
for _ in range(N):
    matrix.append(list(map(int,input().split())))

dx = [-1,0,1,0]
dy = [0,1,0,-1]
 #d가 0이면 북쪽 (-1,0), 1이면 동쪽 (0,1)
 	# 2면 남쪽 (1,0), 3이면 서쪽(0,-1)

count = 1	# 청소한 타일 갯수 저장하는 변수
#청소기는 항상 더러운 타일에 놓여지므로 1부터 시작

x = r
y = c

while True:
    foundway = False
    matrix[x][y] = 2

    for _ in range(4):
        d = (d+3)%4 	# 왼쪽으로 회전
        
        # 전진할 타일의 좌표 nx ny 탐색
        nx = x + dx[d]	
        ny = y + dy[d]

        if 0 < nx < N and 0 < ny < M: # 인덱스 초과를 막는 탐색범위 제한
            if matrix[nx][ny] == 0: # 더러운 타일이면
                # 청소기 nx ny칸으로 전진
                x = nx
                y = ny
                foundway = True	# 더러운 타일 찾았으면 후진 안할거임
                count += 1 # 청소한 타일 갯수 추가
                break
        
    if not foundway:	# 왼쪽으로 네번 회전했는데 더러운 타일이 없을때
    
    	# 후진할 타일의 좌표 nx ny 탐색
        nx = x + dx[(d+2)%4]
        ny = y + dy[(d+2)%4]
        
        if matrix[nx][ny] == 1:	# 후진할 타일이 벽이면
            print(count)
            exit()
        else:
        	 # 벽이 아니면 후진
            x = nx
            y = ny