글 읽기 - 제발 한번만 봐주세요!!!!!!!!!

smu04129 2년 전 0

제발 도와주세요!!

고수님들 도와주세요...

7프로에서 틀렸다 나오네요..

#include <iostream>
#include <cstring>
#include <vector>
#include <limits>
#include <queue>
#define MAX 100
using namespace std;

struct Coord { int y, x; }; //좌표 구조체 행, 열

int N, Num = 0, Answer = numeric_limits<int>::max(); //배열 크기, 섬 테두리를 채워줄 변수, 정답
int Map[MAX][MAX], Boundary[MAX][MAX]; //맵, 경계선
bool Visit[MAX][MAX]; //경계선 만들기 할때 사용할 방문기록배열
int Dir[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }; // 북, 남, 서, 동
vector<Coord> C, V; //섬 좌표, 각 섬 경계선들 좌표

bool range(int y, int x) { //해당 좌표가 범위 안에 들어왔는지 체크용
	if (y >= 0 && y < N && x >= 0 && x < N) { return true; }
	return false;
}

void make_boundary(int y, int x) { //경계선을 만드는 함수
	if (Visit[y][x]) { return; } //이미 방문한 곳이면 빠져나감
	Num++; //경계선 번호
	Visit[y][x] = true; //첫지점 방문기록
	queue<Coord> q({ { y, x } }); //첫 지점 인큐
	while (!q.empty()) {
		auto front = q.front(); 
		q.pop();
		for (int i = 0; i < 4; i++) { //인접한 칸으로 이동
			auto ny = front.y + Dir[i][0], nx = front.x + Dir[i][1];
			if (range(ny, nx)) { //이동한좌표가 범위내에 있다면
				if (Map[ny][nx] == 1 && !Visit[ny][nx]) { //방문한 곳이 아니고 섬이라면 인큐
					Visit[ny][nx] = true;
					q.push({ ny, nx });
				}
				else if (Map[ny][nx] == 0 && Boundary[ny][nx] == 0) { //섬에 붙어있는 바다면서 경계선 표시가 아직 안된곳이라면
					Boundary[ny][nx] = Num;
					V.push_back({ ny, nx }); //경계선 좌표를 추기
				}
			}
		}
	}
}

void make_bridge(int y, int x, int num) { //다리를 건설하는 함수(좌표, 몇번 경계선인지)
	int cnt = 1; //먼저 다리를 놓으면서 시작하기 때문에 1부터 카운트
	queue<Coord> q({ { y, x } }); //경계선의 시작점
	bool visit[MAX][MAX]; //다리를 건설할때 체크할 방문 기록용 배열
	memset(visit, false, sizeof(visit));
	visit[y][x] = true; //첫지점 체크
	while (!q.empty()) {
		int size = q.size();
		while (size--) {
			auto front = q.front();
			q.pop();
			if (Boundary[front.y][front.x] != 0 && Boundary[front.y][front.x] != num) { 
				Answer = cnt; //경계선이면서 함수 파라미터인num번 경계선이 아닌 다른 경계선에 도달한경우
				return; 
			}
			for (int i = 0; i < 4; i++) {
				auto ny = front.y + Dir[i][0], nx = front.x + Dir[i][1];
				if (range(ny, nx) && Map[ny][nx] == 0 && !visit[ny][nx]) {
					visit[ny][nx] = true; // 범위 내에 들어오고 맵에서 바다부분이면서 방문 하지 않은곳이라면
					q.push({ ny, nx });
				}
			}
		}
		cnt++;
		if (cnt >= Answer) { return; } //cnt가 이미 기록된 정답이상일경우 더 탐색해볼필요가 없기때문에 빠져나옴
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++) { 
			cin >> Map[i][j]; 
			if (Map[i][j] == 1) { C.push_back({ i, j }); } //섬인 부분의 좌표를 모두 저장함
		}
	for (const auto c : C) { make_boundary(c.y, c.x); } //저장한 섬좌표를 쭉돌며 경계선을 만들어줌
	for (const auto v : V) { make_bridge(v.y, v.x, Boundary[v.y][v.x]); } //경계선의 좌표를 돌며 다리를 만들음
	cout << Answer;
}

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

문제

문제

출처

ICPC

제발 한번만 봐주세요!!!!!!!!!

smu04129 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말