[BJ14503] 로봇 청소기

🚩 문제 설명

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

14503번: 로봇 청소기

⏱️ 시간 복잡도
▪O(N x M x 4)

◾ 방향은 북, 동, 남, 서 순으로 0123 입니다.

◾ 현재 위치를 먼저 청소를 해야합니다.

◾ 그리고나서 현재 위치에서 바로 왼쪽 칸이 청소를 하지 않았다면 왼쪽으로 회전하고 그 칸으로 이동합니다.

◾ 만약 해당 칸이 청소가 되어있거나, 벽이라서 왼쪽으로 회전을 4번 했다면 후진합니다.

◾ 그러나, 뒤쪽이 벽이라면 그냥 멈춥니다.

 

 

 

---

 

 

 

✅ 입출력

변수 설명

n m : 세로 x 가로

r c d : (로봇청소기 초기 좌표), 바라보는 방향 (0:북, 1:동, 2:남, 3:서)

장소의 상태 (0:빈칸, 1:벽) : n개의 줄

return 로봇 청소기가 청소하는 칸의 갯수

✔️ 예제 1

3 3
1 1 0
1 1 1
1 0 1
1 1 1

1

✔️ 예제 2

11 10
7 4 0
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 1 1 1 0 1
1 0 0 1 1 0 0 0 0 1
1 0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

57

✔️ 예제 3

4 5
1 1 0
1 1 1 1 1
1 0 0 0 1
1 0 1 0 1
1 1 1 1 1

5

✔️ 예제 4

3 3
1 1 0
1 1 1
0 0 0
0 1 1

3

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

import sys

#sys.stdin = open('input.txt', 'rt')
input = sys.stdin.readline
n, m = map(int, input().split())  # 세로 x 가로
r, c, d = map(int, input().split())  # (r, c) d
mp = [list(map(int, input().split())) for _ in range(n)]  # 맵

# 북,동,남,서
# 상(0) -> 좌(3) -> 하(2) -> 우(1) -> 상(0)
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]


def move(x, y, d, cnt):
    global ans

    if cnt == 4:
        d_ = (d + 2) % 4
        x_ = x + dx[d_]
        y_ = y + dy[d_]

        if mp[x_][y_] != 1: # 벽이 아니라면
            move(x_, y_, d, 0)

        return
        
        # 벽이라면 작동을 멈춘다
        # if mp[x_][y_] == 1:
        #     return
        # else:  # 그렇지않으면 한칸 후진
        #     move(x_, y_, d, 0)
        #     return

    d = (d - 1) % 4  # 현재 방향에서 왼쪽으로
    x_ = x + dx[d]
    y_ = y + dy[d]

    # 바깥의 범위라면
    if any([x_ < 0, x_ > n - 1, y_ < 0, y_ > m - 1]):
        return

    # 만약 청소되지 않았다면
    if mp[x_][y_] == 0:
        mp[x_][y_] = -1  # 청소 처리
        ans += 1
        move(x_, y_, d, 0)
    # 만약 벽이라면
    else:
        move(x, y, d, cnt + 1)


if __name__ == '__main__':
    ans = 1  # 로봇청소기가 청소하는 총 칸의 수
    mp[r][c] = -1  # 초기 위치 청소 처리
    move(r, c, d, 0)

    print(ans)

💬 Point

➡️  dfs 를 사용
➡️  제자리에서 회전하는 횟수를 센다 : cnt

◾ pypy3 로 제출해야 합니다. 그렇지 않으면 런타임 에러가 뜹니다.

 

input = sys.stdin.readline
n, m = map(int, input().split())  # 세로 x 가로
r, c, d = map(int, input().split())  # (r, c) d
mp = [list(map(int, input().split())) for _ in range(n)]  # 맵

◾ 입력을 받습니다.

 

# 북,동,남,서
# 상(0) -> 좌(3) -> 하(2) -> 우(1) -> 상(0)
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

◾ 위에서 왼쪽으로 회전하면 왼쪽을 바라보게 되고, 다시 왼쪽으로 회전하면 아래, 또 왼쪽으로 회전하면 오른쪽이 됩니다.

문제를 보면 북동남서 순으로 0123 입니다. 헷갈리지 않게 문제에서 그 순으로 나열되어 있으므로 그렇게 해도 됩니다.

 

if cnt == 4:
    d_ = (d + 2) % 4
    x_ = x + dx[d_]
    y_ = y + dy[d_]

    if mp[x_][y_] != 1:  # 벽이 아니라면
        move(x_, y_, d, 0)

    return

◾ 제자리에서 회전하는 횟수를 cnt 로 셉니다. 만약 그 횟수가 4가 되면 후진을 할지말지 결정을 해야합니다.

상 ↔ 하, 좌 ↔ 우 핑퐁되므로 방향을 (d + 2) % 4 를 해야합니다.

만약 뒷편이 벽이 아니라면 (즉, 0이거나 청소를 한 구역이라면) 해당 칸으로 이동을 하고 회전횟수는 0으로 초기화가 됩니다.

벽을 만나는 경우에는 return 이 됩니다.

 

# 바깥의 범위라면
if any([x_ < 0, x_ > n - 1, y_ < 0, y_ > m - 1]):
    return

◾ 만약 바깥 범위라면 return 을 합니다.

 

# 만약 청소되지 않았다면
if mp[x_][y_] == 0:
    mp[x_][y_] = -1  # 청소 처리
    ans += 1
    move(x_, y_, d, 0)
# 만약 벽이라면
else:
    move(x, y, d, cnt + 1)

◾ 만약 청소가 되지 않았다면 청소 처리를 해줍니다. 저는 -1 로 처리를 했습니다.

그리고 청소를 했으므로 ans 를 +1 해줍니다.

그리고 다음 칸으로 회전을 하고 이동을 합니다.

그렇지 않은 경우에는 다음 칸으로 이동하지 않습니다. 제자리에서 회전을 하고 횟수를 카운팅 해줍니다.

 

if __name__ == '__main__':
    ans = 1  # 로봇청소기가 청소하는 총 칸의 수
    mp[r][c] = -1  # 초기 위치 청소 처리
    move(r, c, d, 0)

    print(ans)

◾ 처음 자리를 우선적으로 청소를 하므로 카운팅을 해줘야합니다. ans가 1로 초기화 되어야 합니다.

그리고 해당 위치를 청소 처리 해줍니다.

그리고 dfs 재귀를 하러 들어갑니다.

 

 

with 자바 (Java)

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


// ry, rx, rd: 로봇 청소기 위치, 방향 
public class Main {
	static int ans, N, M, ry, rx, rd;
	static int turn;
	static int[][] map;

	// 상우하좌
	static int[] dy = { -1, 0, 1, 0 };
	static int[] dx = { 0, 1, 0, -1 };


	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine());
		ry = Integer.parseInt(st.nextToken());
		rx = Integer.parseInt(st.nextToken());
		rd = Integer.parseInt(st.nextToken());

		map = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) map[i][j] = Integer.parseInt(st.nextToken());
		}

		// 초기화
		ans = 1;
		turn = 0;
		map[ry][rx] = 3;

		// 시뮬레이션
		while (true) {
			if (turn == 4) {
				// 후진이 가능하다면 후진
				int backDir = turnBack();

				int ny = ry + dy[backDir];
				int nx = rx + dx[backDir];

				if (ny < 0 || ny >= N || nx < 0 || nx >= M) break;
				if (map[ny][nx] == 1) break;

				ry = ny;
				rx = nx;
				turn = 0;
				continue;
			}

			turnLeft();
			turn++;

			int ny = ry + dy[rd];
			int nx = rx + dx[rd];

			if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
			if (map[ny][nx] == 1) continue;

			if (map[ny][nx] == 0) {
				ry = ny;
				rx = nx;

				map[ny][nx] = 3; // 청소 처리
				turn = 0;
				ans++;
			}

		}

		System.out.println(ans);

	} // end main


	private static void turnLeft() {
		rd = (rd + 3) % 4;
	} // end turnLeft


	private static int turnBack() {
		return (rd + 2) % 4;
	}

}

• 우선 왼쪽으로 돌고 봅니다.
• turn 이 4번이 되면, 후진이 가능하다면 후진을 하고 그렇지 못하다면 바로 break 를 합니다.

 

 

 

+ 비슷한 문제

https://yeomss.tistory.com/105

[TC0404] [구현] 게임 개발

 

 

 

 

 

 

 

# 알고리즘 백준 BJ14503 로봇청소기 파이썬

# 알고리즘 백준 로봇 청소기 python dfs

# 백준 로봇 청소기 java

---