글 읽기 - 2146 다리 만들기 - 틀린 이유 지적 부탁드립니다.

10jobss 6년 전 0

10% 정도에서 틀렸습니다를 받았습니다.

로직은 다음과 같습니다.

1. 섬끼리 그룹번호 부여

(이 때 섬의 한개 좌표를 q_start에 push해 주었습니다. 함수 종료 후 섬의 dist[i][j]값은 0으로 바다의 dist[i][j]값은 -1인 상태입니다.)

2. bfs를 통해 각 그룹 번호로 섬의 영역을 확장

다음 영역이 바다가 아니면서 그룹번호가 다른경우 ans에 거리를 넣었습니다. (각 섬 영역이 치우치게? 시작하는 경우를 고려해서 바로 return 하지 않았습니다)

잘못된 부분 혹은 반례 부탁드립니다.

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define INF 987654321
using namespace std;
typedef pair<int, int> pii;
int n, ans=INF, arr[100][100], dist[100][100];
bool chk[100][100];
int dy[4] = { -1,0,1,0 }, dx[4] = { 0,1,0,-1 };
queue<pii> q, q_start;
bool bnd(int y, int x) {
	return y >= 0 && y < n && x >= 0 && x < n;
}
void color(int y, int x, int c) {
	q_start.push(make_pair(y, x));
	chk[y][x] = true;
	arr[y][x] = c;
	dist[y][x] = 0;
	q.push(make_pair(y, x));
	while (!q.empty()) {
		pii cur = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = cur.first + dy[i];
			int nx = cur.second + dx[i];
			if (!bnd(ny, nx)) continue;
			if (arr[ny][nx] == 0) continue;
			if (chk[ny][nx]) continue;
			chk[ny][nx] = true;
			arr[ny][nx] = c;
			dist[ny][nx] = 0;
			q.push(make_pair(ny, nx));
		}
	}
}
void bfs() {
	while (!q_start.empty()) {
		pii cur = q_start.front();
		q_start.pop();
		for (int i = 0; i < 4; i++) {
			int ny = cur.first + dy[i];
			int nx = cur.second + dx[i];
			if (!bnd(ny, nx)) continue;
			if (arr[ny][nx] != 0 && arr[ny][nx] != arr[cur.first][cur.second]) {
				chk[ny][nx] = true;
				ans = min(ans, dist[ny][nx] + dist[cur.first][cur.second]);
				continue;
				//return;
			}
			if (chk[ny][nx]) continue;
			if (arr[cur.first][cur.second] == arr[ny][nx]) {
				chk[ny][nx] = true;
				q_start.push(make_pair(ny, nx));
			}
			else if (arr[ny][nx] == 0) {
				arr[ny][nx] = arr[cur.first][cur.second];
				chk[ny][nx] = true;
				dist[ny][nx] = dist[cur.first][cur.second] + 1;
				q_start.push(make_pair(ny, nx));
			}
		}
	}
}
int main() {
	scanf("%d", &n);
	int i, j;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) scanf("%d", &arr[i][j]);
	}
	memset(dist, -1, sizeof(dist));
	int cc = 1;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			if (arr[i][j] == 1 && !chk[i][j]) {
				color(i, j, cc++);
			}
		}
	}
	memset(chk, 0, sizeof(chk));
	bfs();
	printf("%d", ans);
	return 0;
}

10
1 1 1 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0 0
0 0 0 0 0 0 1 1 0 0
0 0 0 0 1 0 1 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0

답:3

출력:4

~~코드 읽기 구찮아서 반례 몇개 넣어봄 ㅎㅎ 7행 3열 1 지웠다 넣으면 답이 2 뛰는걸 볼수 있음~~

10jobss 6년 전 0

@atomzeno

반례 감사합니다. 제 코드가 BFS가 아닌? BFS였군요.

해결했습니다!

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

문제

문제

출처

ICPC

2146 다리 만들기 - 틀린 이유 지적 부탁드립니다.

10jobss 6년 전 0

atomzeno 6년 전 1

10jobss 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말