글 읽기 - [C++] 100%에서 틀렸다고 뜨는데 반레하나만 찾아주세요

jabbong 3년 전 1

아래 코드가 그 문제의 코드이구요.

모든 칸을 순회하면서 아래와 같은 과정을 반복하였습니다.

1. 이 칸이 육지에 속하는 가

이 칸이 육지에 속해야 지만 다리를 놓을 수 있기 때문입니다.

2. 이 칸이 바다에 한 면이라도 접해 있는가

이 칸이 바다에 한 면이라도 접해 있어야지 다리를 놓을 수 있기 때문입니다.

3. 이 칸이 속해 있는 대륙을 모두 방문 표시

이 칸이 속해 있는 대륙을 모두 방문 표시하여 다리가 이 대륙에서 시작하여 이 대륙으로 끝나는 다리로 만들어지는 것을 방지하기 위해 모두 방문 표시 하였습니다.

4. BFS 시작

이 칸에 대하여 BFS 를 시작합니다.

BFS를 하다가 그 자리가 육지이고 방문하지 않았으면(다른 대륙이라면) 탐색을 종료합니다.

이름도 설명드리겠습니다.

ca 배열 : 지금 체크할 칸이 속해있는 대륙의 칸을 모두 1로 저장하는 배열입니다.

q : BFS에서 그 칸의 좌표(x, y)를 저장하고 있습니다.

step : BFS에서 그 칸과 다리의 시작 칸과의 거리를 저장하고 있습니다.

ans : 놓을 수 있는 다리의 길이의 최솟값을 저장하였다가 모든 칸을 순회하면 출력하는 변수입니다.
n : 지도의 크기를 저장하는 변수입니다.

check 함수 : 입력으로 주어진 칸이 지도의 범위를 넘어가는지 안 넘어가는 지를 판단하고 그 칸이 바다면 1, 육지면 2를 리턴하는 함수입니다.

go 함수 : BFS의 반복되는 (위쪽, 아래쪽, 오른쪽, 왼쪽) 칸에 대한 처리를 하기 위한 함수입니다.

이 코드는 제출하니까 100%에서 틀렸다고 뜨네요...

이 코드에 문제점이나 반레를 찾아주세요!!!!

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int n, a[100][100], ans = 100000, ca[100][100];
queue<pair<int, int>> q;
queue<int> step;

// 입력으로 주어진 칸이 지도의 범위를 넘어가는지 안 넘어가는지 판단하고 그 칸이 바다면 1, 육지면 2를 리턴하는 함수
int check(int x, int y) {
	if (0 <= x && x < n && 0 <= y && y < n) {
		if (a[y][x] == 0) return 1;
		if (a[y][x] == 1) return 2;
	}
	return 0;
}

// BFS의 반복되는 (위쪽, 아래쪽, 오른쪽, 왼쪽) 칸에 대한 처리를 하기위한 함수
int go(int x, int y, int t) {
	if (check(x, y)) {
		if (ca[y][x] == false) {
			if (a[y][x] == 1) {
				ans = min(ans, t);
				return 1;
			}
			else {
				q.push({ x, y });
				step.push(t + 1);
				ca[y][x] = true;
			}
		}
	}
	return 0;
}

int main() {
	// 입력
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}

	// 모든 칸 순회
	for (int y = 2; y < n; y++) {
		for (int x = 2; x < n; x++) {
			// 이 칸이 육지에 속하는가
			if (a[y][x] == 0) continue;
			bool ok = false;

			// 이 칸이 바다에 한면이라도 접해있는가
			if (check(x, y - 1) == 1) ok = true;
			if (check(x, y + 1) == 1) ok = true;
			if (check(x - 1, y) == 1) ok = true;
			if (check(x + 1, y) == 1) ok = true;
			if (ok == false) continue;

			// ca 배열(방문했는지 확인 배열) 초기화
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					ca[i][j] = false;
				}
			}

			// 큐 초기화
			while (!q.empty()) {
				q.pop();
				step.pop();
			}

			// 이 칸이 속해 있는 대륙을 모두 방문 표시
			q.push({ x, y });
			ca[y][x] = true;
			while (!q.empty()) {
				int u = q.front().first;
				int v = q.front().second;
				q.pop();
				if (ca[v - 1][u] == false && check(u, v - 1) == 2) {
					q.push({ u, v - 1 });
					ca[v - 1][u] = true;
				}
				if (ca[v + 1][u] == false && check(u, v + 1) == 2) {
					q.push({ u, v + 1 });
					ca[v + 1][u] = true;
				}
				if (ca[v][u - 1] == false && check(u - 1, v) == 2) {
					q.push({ u - 1, v });
					ca[v][u - 1] = true;
				}
				if (ca[v][u + 1] == false && check(u + 1, v) == 2) {
					q.push({ u + 1, v });
					ca[v][u + 1] = true;
				}
			}

			// BFS 탐색 시작
			q.push({ x, y });
			step.push(0);
			ca[y][x] = true;
			while (!q.empty()) {
				int u = q.front().first;
				int v = q.front().second;
				int t = step.front();
				q.pop();
				step.pop();
				if (go(u, v - 1, t)) break;
				if (go(u, v + 1, t)) break;
				if (go(u - 1, v, t)) break;
				if (go(u + 1, v, t)) break;
			}
		}
	}

	// 작은 값 출력
	cout << ans;
	return 0;
}

wjdgud0621 3년 전 1

48~49번째 줄이 이상하네요

jabbong 3년 전 1

정말 사소한 실수를 하였네요....

48줄과 49줄에 0으로 다 해야하는데 (2, 2)에 대한 BFS가 동작하는지 테스트 할려고, 했던것으로 바꾸지도 않고 제출하였네요...

jabbong 3년 전 2

wjdgud0621님, 정말 감사합니다!!!!!!!!

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

문제

문제

출처

ICPC

[C++] 100%에서 틀렸다고 뜨는데 반레하나만 찾아주세요

jabbong 3년 전 1

wjdgud0621 3년 전 1

jabbong 3년 전 1

jabbong 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말