[백준] 14503. 로봇 청소기 (파이썬)

문제

로봇 청소기

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

 

시간 제한 2초

메모리 제한 512MB

 

• 공간의 크기 N x M
• 로봇 청소기는 바라보는 방향이 있다.
  • 0 : 북, 1 : 동, 2 : 남, 3 : 서
• 각 칸의 상태는 숫자로 표시됨
  • 0 : 빈칸,  1 : 벽(이동 불가)
•  로봇 청소기의 작동 방식

1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.     

      a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.

      b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.

      c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.

      d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

 

   로봇 청소기는 이미 청소되어 있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.

---

풀이

완전탐색 알고리즘들(브루트포스, bfs, dfs 등)중, 

주어진 공간 전부를 탐색하지 않고, 로봇청소기가 조건에 맞게 이동할 수 있는 경로만을 탐색하므로

DFS(재귀) 스타일이 가장 적합하다고 생각했다.

 

 

이 문제에서의 핵심 구현 포인트는 두 가지이다.

1. 방향 회전을 어떻게 할까?

# 0: 북, 1: 동, 2: 남, 3: 서
# dx = [-1, 0, 1, 0]	
# dy = [0, 1, 0, -1]
# 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.
	new_d = d
	for _ in range(4):
		#왼쪽 방향부터 탐색
		new_d = (new_d + 3) % 4
		nx = x + dx[new_d]
		ny = y + dy[new_d]

로봇청소기의 방향 정보(d)가 int 입력값이므로

해당 값을 방향벡터의 index로 활용할 수 있도록 dx, dy 리스트를 저장하였다.

 

방향을 왼쪽으로 회전하는 방법은

new_d 값에서 -1을 더해주거나, 3을 더해주는 방법이 있다.

 

하지만 0에서 -1을 하게 될 경우, 별도의 값 처리가 필요하므로 

3을 더해주는 방식을 채택하였다.

 

2. 후진을 어떻게 할까?

#c. 네 방향 모두 청소가 되어 있는 경우: 바라보는 방향을 유지한 채로 한칸 후진.
	bx = x - dx[d]
	by = y - dy[d]
	
	if board[bx][by] != 1:
		dfs(bx, by, d)
	#d. 이때, 후진 불가능한 경우: 탐색 종료
	return

위와 같은 방식으로 후진을 위해

 

(new_d + 2) % 4 를 계산하여 이용하는 방법도 있었지만,

위와 같은 방법으로 기존 좌표에서 값을 빼 주면 

d값을 유지하면서 반대 방향으로 이동이 가능하다.

 

코드

import sys

input = sys.stdin.readline

'''
풀이 방법: DFS
시간 복잡도 : O(n^4) 
공간 복잡도 : O(n^2)
'''

def dfs(x, y, d):
	global res
    #1. 현재 위치를 청소한다. 
    #청소 시, 청소하지 않은 칸과 구분을 위해 값을 2로 갱신해주었다.
	if not board[x][y]:
		board[x][y] = 2
		res += 1
    
    #2. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.
	new_d = d
	for _ in range(4):
		#왼쪽 방향부터 탐색
		new_d = (new_d + 3) % 4
		nx = x + dx[new_d]
		ny = y + dy[new_d]

		#청소 가능한 칸을 발견하면
		if not board[nx][ny]:
			dfs(nx, ny, new_d)
			return
    
    #c. 네 방향 모두 청소가 되어 있는 경우: 바라보는 방향을 유지한 채로 한칸 후진.
	bx = x - dx[d]
	by = y - dy[d]
	
	if board[bx][by] != 1:
		dfs(bx, by, d)
	#d. 이때, 후진 불가능한 경우: 탐색 종료
	return

    
if __name__ == "__main__":
	n, m = map(int, input().rstrip('\n').split())
	r, c, d = map(int, input().rstrip('\n').split())
	board = []

	for i in range(n):
		board.append(list(map(int, input().rstrip('\n').split())))
		
    #d값에 맞게 방향벡터 설정
	dx = [-1, 0, 1, 0]
	dy = [0, 1, 0, -1]

	res = 0 
    #로봇 청소기 작동
	dfs(r, c, d)

	print(res)

 

삼성 기출 문제들 중 구현, 시뮬레이션 문제들은 문제 길이가 정말 긴 편이다.

문제를 꼼꼼하게 읽고, 요구사항에 맞게 차근차근 구현하면 된다.