[백준 14503] 로봇 청소기 (C++/Python)

1. 입력

- 3 <= n,m < 50

- n, m, d (방향)

2. 출력

- 청소하는 칸의 개수

3. 조건

- 방향 : 0 - 북쪽, 1 - 동쪽, 2 - 남쪽, 3 - 서쪽

- 모든 모서리는 벽

4. 반례

4 4
1 1 0
1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1
// 4

4 6
2 3 1
1 1 1 1 1 1
1 0 1 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
// 4

 

5. 알고리즘

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.

2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
  2.1 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.

    → 청소되어 있는 칸이라도 후진할 수 있다면 후진한다.

  2.2 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.

3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,

  3.1 반시계 방향으로 90도 회전한다.

  3.2 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.

    → 청소 되어있는 칸이라면 새로운 방향으로 탐색을 다시 시작한다.

  3.3 1번으로 돌아간다.

 

---

 

C++)

#include <iostream>
#include <queue>
#define MAX_NUM 52
using namespace std;

struct data {
	int x;
	int y;
	int d;
};

int dx[4] = { -1,0,1,0};
int dy[4] = { 0,1,0,-1 };
queue<struct data> q;
int arr[MAX_NUM][MAX_NUM];
bool visited[MAX_NUM][MAX_NUM];

int n, m;

bool FindNotCleanArea(int x, int y) {
	for (int k = 0; k < 4; k++) {
		int nx = x + dx[k];
		int ny = y + dy[k];

		if (arr[nx][ny] == 0 && !visited[nx][ny])
			return true;
	}

	return false;
}

int TurnMinus90(int dir) {
	if (dir >= 1)
		return dir - 1;
	else 
		return 3;
}

int GoBack(int dir) {
	if (dir % 2 == 0)
		return 2 - dir;
	else 
		return 4 - dir;
}

int bfs() {
	int ans = 0;
	bool flag = true;

	while (flag && !q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int d = q.front().d;
		q.pop();

		// 1. 칸 청소 안 되어있으면 청소한다.
		if (!visited[x][y]) {
			visited[x][y] = true;
			ans++;
		}

		// 주변 4칸의 청소여부를 확인한다
		bool isClean = FindNotCleanArea(x, y);

		// 2. 청소되지 않은 빈 칸이 없다
		if (!isClean) {
			int newDir = GoBack(d);
			int nx = x + dx[newDir];
			int ny = y + dy[newDir];

			// 2.1 후진할 수 있다면 후진
			if (arr[nx][ny] == 0)
				q.push({ nx,ny,d });
			// 2. 뒷쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다
			else
				flag = false;
		}
		// 3. 있다
		else {
			int newDir = TurnMinus90(d);	// 3.1 반시계방향
			int nx = x + dx[newDir];
			int ny = y + dy[newDir];

			// 3.2 청소되지 않은 빈칸인 경우 전진
 			if (arr[nx][ny] == 0 && !visited[nx][ny])
				q.push({ nx,ny,newDir });
			else
				q.push({ x, y, newDir });
		}
	}

	return ans;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m;

	int x, y, d;
	cin >> x >> y >> d;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			cin >> arr[i][j];
	}

	q.push({ x,y,d });

	cout << bfs();

	return 0;
}

 

 

 

Python)

* 주석은 C++ 참고

import sys
from collections import deque

read = sys.stdin.readline

q = deque()
dx = [-1,0,1,0]
dy = [0,1,0,-1]

n, m = map(int, read().rstrip().split())
x, y, d = map(int, read().rstrip().split())
arr = [ [0] * m for _ in range(n)]
visited = [ [False] * m for _ in range(n)]

def turn_minus_90(dir):
    if dir > 0:
        return dir - 1
    return 3

def go_back(dir):
    if dir % 2 == 0:
        return 2-dir
    return 4 - dir

def find_not_clean_area(x, y):
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]

        if arr[nx][ny] == 0 and not visited[nx][ny]:
            return True
    return False

def bfs():
    flag = True
    ans = 0

    while flag and q:
        x, y, d = q.popleft()

        if not visited[x][y]:
            visited[x][y] = True
            ans += 1

        is_clean = find_not_clean_area(x, y)

        if is_clean:
            new_dir = turn_minus_90(d)
            nx = x + dx[new_dir]
            ny = y + dy[new_dir]

            if arr[nx][ny] == 0 and not visited[nx][ny]:
                q.append((nx,ny,new_dir))
            else:
                q.append((x,y,new_dir))
        else:
            new_dir = go_back(d)
            nx = x + dx[new_dir]
            ny = y + dy[new_dir]

            if arr[nx][ny] == 0:
                q.append((nx,ny,d))
            else:
                flag = False

    return ans

for i in range(n):
    arr[i] = list(map(int, read().rstrip().split()))

q.append((x,y,d))

print(bfs())