글 읽기 - 런타임에러

johyesong8686 4년 전 0

몇시간 째 런타임에러를 못찾고있습니다.

더불어 런타임에러 이외에도 코드에서 불필요한 부분이나

틀린 논리가 있으면 조언해주시면 감사하겠습니다. ㅜㅜ

1.dfs를 통해 영역을 섬마다 숫자로 라벨링 했습니다.==>나중에 bfs로 전진할시에 자기섬이 아닌 다른 섬을 구분하기 위해서

2.섬에서 각 끝부분 바다와 인접한 부분의 좌표를 구한뒤 queue에 넣었습니다.(섬의 갯수 만큼)

3.queue에 넣는 부분을 빼면서 bfS를 돌리면서 다른 섬에 도달할시에 만큼의 반복한 횟수의 최솟값을 구했습니다.

#include <iostream>
#include <queue>
#include <cstring>
#define MAX 101
using namespace std;
int map[MAX][MAX];
int check[MAX][MAX];
int dist[MAX][MAX] = { 0, };
queue <pair<int, int> > p;

int color = 0;
int N;
int x[] = { -1,0,+1,0 };
int y[] = { 0,-1,0,+1 };

bool numbercheck(int i, int j) {
	if (i < 0 || i >= N || j < 0 || j >= N) {
		return true;
	}
	else {
		return false;
	}
}
//영역 나누기
void dfs(int i, int  j) {
	map[i][j] = color;
	check[i][j] = 1;
	for (int k = 0; k < 4; k++) {
		int newX = x[k] + i;
		int newY = y[k] + j;
		if (check[newX][newY] == 0 && map[newX][newY] == 1 && (!numbercheck(newX, newY))) {
			dfs(newX, newY);

		}
	}
}


queue<pair<int, int> > q[MAX];
int result = MAX;
int main(void) {

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

			if (map[i][j] == 1 && check[i][j] == 0) {
				color++;
				dfs(i, j);


			}

		}
	}
	memset(check, 0, sizeof(check));
	/*for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout<<map[i][j];
		}
		cout << '\n';
	}*/ //영역 잘 나눠졌는지 확인

	//끝지점 좌표 구하기
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 0) {
				continue;
			}
			else if (check[i][j] == 1) {
				continue;
			}
			else {
				check[i][j] = 1;

				for (int k = 0; k < 4; k++) {
					int newX = x[k] + i;
					int newY = y[k] + j;
					if (numbercheck(newX, newY)) {
						continue;
					}

					else if (map[newX][newY] == 0 && check[newX][newY] == 0) {
						check[newX][newY] = 1;
						q[map[i][j]].push(make_pair(i, j));
						//cout << "i:" << i << "j:" << j << '\n';

						break;

					}

				}
			}
		}
	}
	memset(check, 0, sizeof(check));

	//bfs 를 통해 좌표이동
	queue <pair<int, int> > pq;
	/*for (int i = 1; i <= color; i++) {
		while (!q[i].empty())
		{
			cout << "i:" << "first " << q[i].front().first << " second " << q[i].front().second << '\n';
			q[i].pop();
		}


		cout << "---------------" << '\n';
	}*/


	for (int i = 1; i < color; i++) {
		int A;
		int B;
		
		while (!q[i].empty())
		{
			A = q[i].front().first;
			B = q[i].front().second;
			pq.push(make_pair(A, B));
			check[A][B] = 1;
			q[i].pop();
		}
		
		while (!pq.empty()) {
			int X = pq.front().first;
			int Y = pq.front().second;

			pq.pop();

			int newX;
			int newY;

			for (int k = 0; k < 4; k++) {
				newX = X + x[k];
				newY = Y + y[k];

				if (numbercheck(newX, newY)) continue;
				if (map[newX][newY] == map[A][B])
					continue;
				if (check[newX][newY] == 1)
					continue;


				if (map[newX][newY] == 0) {
					pq.push(make_pair(newX, newY));
					check[newX][newY] = 1;

					if (dist[newX][newY] == 0) {

						dist[newX][newY] = dist[X][Y] + 1;

					}
				}
				else if (map[newX][newY] != 0) {
					result = min(result, dist[X][Y]);

				}

			}

		}

	}


	cout << result << '\n';





	return 0;
}

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

문제

문제

출처

ICPC

런타임에러

johyesong8686 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말