글 읽기 - 아무리 생각해도 맞는것 같습니다. (게시판 모두 정독, 찾아본 반례 다 통과)

iron1209 5년 전 3

제가 이 문제를 풀어보려고 거의 8시간정도 쓴 것 같습니다. 처음 코드를 짯을때도 계속 틀렸습니다 나와서 2번정도 새로 코드를 짯습니다.

한참을 찾으면서 다른 코드와 비교해보고 확인도 해 보았습니다. 예시와 반례도 이 게시판 모두 다 뒤져 보면서 입력해 보았지만 모두 정답이 나왔습니다.

하지만 계속 채점에서만 틀리게 나오고 있습니다. 현명한 답변을 부탁드립니다. (시간초과는 확실히 아닙니다.)

#include<stdio.h>
int n, m;
int A[105][105], B[105][105];
int queue[100000][3];
void bfs(int a, int b) {
	int front, rear, count;
	front = rear = count = 0;
	queue[0][0] = a;
	queue[0][1] = b;
	queue[0][2] = 1;
	B[a][b] = 1;
	rear++;
	while (front < rear) {
		a = queue[front][0];
		b = queue[front][1];
		count = queue[front][2];
		if (a == n && b == m) {
			printf("%d", count);
			return;
		}
		B[a][b] = 1;
		front++;
		if (A[a][b + 1] == 1 && B[a][b + 1] == 0) {
			queue[rear][0] = a;
			queue[rear][1] = b + 1;
			queue[rear][2] = count + 1;
			rear++;
		}
		if (A[a][b - 1] == 1 && B[a][b - 1] == 0) {
			queue[rear][0] = a;
			queue[rear][1] = b - 1;
			queue[rear][2] = count + 1;
			rear++;
		}
		if (A[a + 1][b] == 1 && B[a + 1][b] == 0) {
			queue[rear][0] = a + 1;
			queue[rear][1] = b;
			queue[rear][2] = count + 1;
			rear++;
		}
		if (A[a - 1][b] == 1 && B[a - 1][b] == 0) {
			queue[rear][0] = a - 1;
			queue[rear][1] = b;
			queue[rear][2] = count + 1;
			rear++;
		}
	}
}
int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int i, j;
	scanf("%d %d", &n, &m);
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) {
			scanf("%1d", &A[i][j]);
		}
	}
	bfs(1, 1);
}

wondy1128 5년 전 1

일단 처음 봤을 때 발생한 문제라 생각해서 수정을 했으나 시간초과를 받았습니다.

맵에 대한 경계조건이 없다. Out Of Memory => 경계조건 작성
큐에 push할 수 있는 횟수는 100,000 을 초과할 수 없다. => 원형큐사용
다음으로 생각한 부분은 BFS에 대한 방문이해가 잘못되어있다고 보았습니다.

큐에서 꺼내면서 방문표시를 하는 것이 아닙니다. 큐에 넣으면서 방문표시를 해야합니다. 이유는 처음으로 그 지점을 방문했을 때 현재있는 위치에서 count된 값 + 1 이 최소이기 때문입니다. 만약 그렇지 않고 항상 4방향, 3방향을 큐에 넣게 됩니다. 이때 맵이 작을 경우 "틀렸습니다." 맵이 클 경우 "시간초과"를 받게 될 수 있습니다.

아래는 코드를 첨부합니다.

#include<stdio.h>
int n, m;
int A[105][105], B[105][105];
int queue[100000][3];
void bfs(int a, int b) {
	int front, rear, count;
	front = rear = count = 0;
	queue[0][0] = a;
	queue[0][1] = b;
	queue[0][2] = 1;
	B[a][b] = 1;
	rear++;
	while (true) {
		a = queue[front][0];
		b = queue[front][1];
		count = queue[front][2];
		if (a == n && b == m) {
			printf("%d", count);
			return;
		}
		// B[a][b] = 1; // delete
		front = (front + 1) % 100000; // add
		if (b + 1 <= m) { // add
			if (A[a][b + 1] == 1 && B[a][b + 1] == 0) {
				queue[rear][0] = a;
				queue[rear][1] = b + 1;
				queue[rear][2] = count + 1;
				B[a][b + 1] = 1;//add
				rear = (rear + 1) % 100000;//add
			}
		}

		if (b - 1 >= 1) { // add
			if (A[a][b - 1] == 1 && B[a][b - 1] == 0) {
				queue[rear][0] = a;
				queue[rear][1] = b - 1;
				queue[rear][2] = count + 1;
				B[a][b - 1] = 1;//add
				rear = (rear + 1) % 100000;//add
			}
		}

		if (a + 1 <= n) { // add
			if (A[a + 1][b] == 1 && B[a + 1][b] == 0) {
				queue[rear][0] = a + 1;
				queue[rear][1] = b;
				queue[rear][2] = count + 1;
				B[a + 1][b] = 1;//add
				rear = (rear + 1) % 100000;//add
			}
		}
		if (a - 1 >= 1) { // add
			if (A[a - 1][b] == 1 && B[a - 1][b] == 0) {
				queue[rear][0] = a - 1;
				queue[rear][1] = b;
				queue[rear][2] = count + 1;
				B[a - 1][b] = 1; //add
				rear = (rear + 1) % 100000; //add
			}
		}

	}
}
int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int i, j;
	scanf("%d %d", &n, &m);
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) {
			scanf("%1d", &A[i][j]);
		}
	}
	bfs(1, 1);
}

jh05013 5년 전 2

게시판을 정말로 모두 정독하셨다면 눈에 띄는 제목의 https://www.acmicpc.net/board/...을 보셨을 것이고, 그 글에서 링크된 FAQ에는 "큐에 넣을 때 방문했음을 바로 표시하는 게 바람직합니다."라고 적혀 있습니다.

iron1209 5년 전 1

답변 해주신분 모두 정말 감사드립니다.

사실 본격적으로 큐를 직접 이용해본건 이 문제가 처음이였습니다.

제가 큐와 문제를 완벽하게 이해를 하지 못했던것 같습니다. 정말 어제 하루 종일 답답했었는데 이렇게 정확하게 해결을 하게 되어서 정말 감사드린다는 생각밖에 안드네요.

저도 여러분 처럼 더 공부해서 나중에 질문 게시판에 다른분 에게 도움이 될 수 있도록 노력하겠습니다. 정말 감사합니다.

iron1209 5년 전 1

그런데 어제부터 궁금해 하던건데요. 다음칸으로 이동하는것의 조건이 A가 1이 있고 한번도 가지 않은곳으로 이동하는것인데요,

예) if (A[a - 1][b] == 1 && B[a - 1][b] == 0)

그런데 A는 모두 전역배열로 설정하여서 n*m칸 주변이 모두 0이므로 지정된 맵을 벗어날 일이 없을것 같은데 맵을 벗어나는지 체크를 할 필요가 있나요? 맵 안에 있는 1로 지정된 곳만 갈것 같은데요.

wondy1128 5년 전 1

그런데 어제부터 궁금해 하던건데요. 다음칸으로 이동하는것의 조건이 A가 1이 있고 한번도 가지 않은곳으로 이동하는것인데요,

예) if (A[a - 1][b] == 1 && B[a - 1][b] == 0)

=> 이 댓글은 맞는 얘기네요. 경계체크부분 코드를 지우고 제출해도 맞습니다.

djm03178 5년 전 2

이 코드의 경우 인덱스를 1에서 n, m까지로 잡고 배열 크기 역시 넉넉하게 설정했기 때문에 그렇게 해도 됩니다. 그렇지만 평소에 조심하는 습관을 들이는 것이 좋습니다.

예를 들어 '방문 불가 지점'을 나타내는 값이 0이 아닐 수도 있고, 많은 경우 인덱스를 1부터 시작하는 것보다 0부터 시작하는 게 편리한 경우가 많습니다. 이런 경우 경계 처리를 하지 않으면 큰 문제가 될 수 있습니다.

iron1209 5년 전 0

답변해주신분 모두 감사드립니다

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

문제

문제

출처

ICPC

아무리 생각해도 맞는것 같습니다. (게시판 모두 정독, 찾아본 반례 다 통과)

iron1209 5년 전 3

wondy1128 5년 전 1

jh05013 5년 전 2

iron1209 5년 전 1

iron1209 5년 전 1

wondy1128 5년 전 1

djm03178 5년 전 2

iron1209 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말