#include #include #include // std::min, std::fill #include // std::vector 사용 (선택 사항이지만 더 현대적) using namespace std; // 최대 맵 크기 const int MAX = 100; // 전역 변수 선언 int N; // 맵의 크기 int board[MAX][MAX]; // 맵 정보 및 섬 번호 (0: 바다, 1: 미처리 육지, 2부터: 섬 번호) int dist[MAX][MAX]; // BFS 탐색 시 각 칸까지의 거리 (다리 길이) // -1: 미방문, 0: 출발 섬 경계 또는 바다 위 출발 지점 // 방향 벡터 (상하좌우) int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; // BFS 큐에 저장할 정보 구조체 struct BridgeState { int x, y; int current_dist; // 현재까지의 다리 길이 (바다를 건넌 칸 수) int initial_island_id; // 이 BFS 탐색이 시작된 섬의 고유 번호 BridgeState(int _x, int _y, int _dist, int _id) : x(_x), y(_y), current_dist(_dist), initial_island_id(_id) {} }; // 1단계: 섬 라벨링 BFS // map 배열의 1을 island_num으로 변경하고 연결된 모든 육지에 동일한 번호 부여 void bfs_label_island(int start_x, int start_y, int island_num) { queue> q; q.push({start_x, start_y}); board[start_x][start_y] = island_num; // 현재 칸에 섬 번호 부여 while (!q.empty()) { pair cur = q.front(); q.pop(); for (int dir = 0; dir < 4; ++dir) { int nx = cur.first + dx[dir]; int ny = cur.second + dy[dir]; // 맵 범위 체크 if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue; // 아직 라벨링되지 않은 육지(1)인 경우 if (board[nx][ny] == 1) { board[nx][ny] = island_num; // 같은 섬 번호 부여 q.push({nx, ny}); } } } } // 2단계: 최단 다리 찾기 Multi-Source BFS int find_shortest_bridge() { queue q_bridge_bfs; // dist 배열을 -1로 초기화 (모든 칸 미방문으로) for (int i = 0; i < N; ++i) { fill(dist[i], dist[i] + N, -1); } // 모든 섬의 경계선 찾기 및 큐에 추가 // 이 단계에서 dist 배열은 0 (출발점) 또는 -1 (미방문)으로 채워짐 for (int r = 0; r < N; ++r) { for (int c = 0; c < N; ++c) { if (board[r][c] > 1) { // 섬(2, 3, ...)인 경우 bool is_boundary = false; for (int dir = 0; dir < 4; ++dir) { int nx = r + dx[dir]; int ny = c + dy[dir]; // 맵 범위 밖이거나 바다인 경우 (경계선) if (nx < 0 || nx >= N || ny < 0 || ny >= N || board[nx][ny] == 0) { is_boundary = true; break; } } if (is_boundary) { // 경계선이라면 큐에 추가 (시작 위치, 거리 0, 해당 섬의 ID) q_bridge_bfs.push(BridgeState(r, c, 0, board[r][c])); dist[r][c] = 0; // 해당 경계선의 다리 길이는 0 } } } } int min_bridge_len = 2 * N * N; // 충분히 큰 값으로 초기화 (최대 N=100이므로 200 * 200 = 40000보다 작음) // Multi-Source BFS 시작 while (!q_bridge_bfs.empty()) { BridgeState current = q_bridge_bfs.front(); q_bridge_bfs.pop(); int x = current.x; int y = current.y; int d = current.current_dist; int current_start_island_id = current.initial_island_id; // 이미 발견된 최소 다리 길이보다 현재 거리가 크거나 같으면 더 탐색할 필요 없음 (가지치기) if (d >= min_bridge_len) continue; for (int dir = 0; dir < 4; ++dir) { int nx = x + dx[dir]; int ny = y + dy[dir]; // 맵 범위 체크 if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue; // 1. 다른 섬에 도착한 경우 // 다음 칸이 육지이고, 그 육지의 섬 번호가 현재 BFS의 출발 섬 번호와 다를 때 if (board[nx][ny] > 1 && board[nx][ny] != current_start_island_id) { // 다른 섬에 도착했으므로, 현재까지의 거리(d)가 다리 길이가 됨 min_bridge_len = min(min_bridge_len, d); // 이 방향으로는 더 이상 탐색할 필요 없음 continue; } // 2. 바다인 경우 (다리를 놓는 중) // 아직 방문하지 않은 칸(dist[nx][ny] == -1)인 경우 if (dist[nx][ny] == -1) { dist[nx][ny] = d + 1; // 거리 갱신 // 큐에 추가: {다음 x, 다음 y, 거리 + 1, 출발 섬 번호는 그대로} q_bridge_bfs.push(BridgeState(nx, ny, d + 1, current_start_island_id)); } } } return min_bridge_len; } int main() { // 입출력 속도 최적화 cin.tie(0)->sync_with_stdio(0); cin >> N; // 맵 입력 받기 for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> board[i][j]; } } // 1단계: 섬 라벨링 (board 배열에 2, 3, ... 번호로 저장됨) // board[i][j] == 1 인 경우에만 bfs_label_island 호출 int island_id = 2; // 섬 번호는 2부터 시작 (0은 바다, 1은 초기 육지) for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (board[i][j] == 1) { // 아직 라벨링되지 않은 육지 발견 bfs_label_island(i, j, island_id); island_id++; } } } // 2단계: 최단 다리 찾기 int result = find_shortest_bridge(); cout << result << endl; return 0; }

제출 #99847

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: