글 읽기 - 14503 로봇청소기 질문입니다.

dkyou7 4년 전 1

코드 진행방향 일일이 체크해보면서 디버깅했는데도 원인을 찾지 못했습니다.

반례를 찾는것을 도와주시면 감사하겠습니다!!

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int dy[] = { -1,0,1,0 };
int dx[] = { 0,1,0,-1 };

int N, M, r, c, d;
int arr[50][50];
void print() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cout << arr[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}
int main() {
	cin >> N >> M >> r >> c >> d;

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

	queue<pair<int, int>>q;
	q.push(make_pair(r, c));
	int count = 0;
	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		if (arr[y][x] == 0) {
			arr[y][x] = 2;
			count++;
		}
		q.pop();
		bool flag = false;
		for (int i = 0; i < 4; i++) {
			int dir = (d + 3) % 4;
			int ny = y + dy[dir];
			int nx = x + dx[dir];

			if (0 <= ny && ny < N && 0 <= nx && nx < M) {
				// 범위 안쪽에 있고
				if (arr[ny][nx] == 0) {
					// 청소할 공간이라면
					q.push({ ny,nx });
					// 추가된 코드. 방향 업데이트해주기!!
					d = dir;
					flag = true;
					break;
				}
				else {
					d = dir;
				}
			}
		}
		if (!flag) {
			int dir = (d + 2) % 4;
			int ny = y + dy[dir];
			int nx = x + dx[dir];
			if (!(0 <= ny && ny < N && 0 <= nx && nx < M) || arr[ny][nx] == 1) {
				break;
			}
			q.push({ ny,nx });
		}
		//print();
	}
	cout << count << endl;

	return 0;
}

seico75 4년 전 1

d도 큐에 넣어줘야하지 않을까요?

dkyou7 4년 전 0

댓글 감사합니다!

저는 방향을 계속 임시변수로 업데이트해주기 때문에 따로 큐에 넣지 않았는데요.

큐에 넣었을 때 저장된 방향이 최신 방향과 다를경우 문제가 될 수 있다는 생각에 밖으로 빼두었습니다.

이게 문제가 될까요??

djm03178 4년 전 1

애초에 큐를 쓸 필요가 없습니다. 다음 방문할 칸은 하나로 결정되어있기 때문에 단순히 다음 칸으로 이동하면 되는 거고, BFs 하듯이 탐색할 필요가 없습니다.

dkyou7 4년 전 0

좋은 의견 감사합니다.

bfs처럼 이용한 이유는 4방향 탐색을 무한히 하기 위해서였습니다.

제가 더 좋은 방법을 알지 못해 bfs로 처리를 하였습니다.

더 좋은 방법을 알려주신다면 공부해보겠습니다.

공부할만한 참고 레퍼런스나 검색어를 알 수 있을까요?

djm03178 4년 전 1

좋은 방법이 따로 있는 게 아니라 지금 하고 계신 거에서 큐만 없애면 됩니다.

큐에 넣자마자 바깥 루프를 돌아 방금 넣은 걸 큐에서 빼서 현재 좌표와 방향으로 설정하고 있는 걸, 큐에 넣지 않고 곧바로 현재 좌표와 방향으로 설정하면 됩니다.

dkyou7 4년 전 0

이해했습니다!

좋은 의견 감사드립니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

14503 로봇청소기 질문입니다.

dkyou7 4년 전 1

seico75 4년 전 1

dkyou7 4년 전 0

djm03178 4년 전 1

dkyou7 4년 전 0

djm03178 4년 전 1

dkyou7 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말