-
BOJ 2146 [다리 만들기]알고리즘 풀이/BFS(너비 우선 탐색) 2018. 10. 4. 06:28
BOJ 다리 만들기 : https://www.acmicpc.net/problem/2146
안녕하세요. 이번 문제는 백준 온라인 저지의 [다리 만들기] 입니다.
1. BFS로 현재 위치에서 갈 수 있는 곳을 확장시킨 뒤, BFS를 빠져나올 때 마다 해당 섬에 번호 부여.
2. 다시 처음부터 BFS를 돌며, 첫 시작지와 섬 번호가 다른 섬을 찾아 떠난다.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485import java.util.*;class Node {public int ori_num, i, j, depth;public Node(int ori_num, int i, int j, int depth) {this.ori_num = ori_num;this.i = i;this.j = j;this.depth = depth;}}public class Main {public static int N;public static int[][] Map = new int[100][100];public static boolean[][] Visited = new boolean[100][100];public static int[][] d = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};public static int island_num = 1; //각각의 섬의 번호public static int Result = 99999999;public static Queue<Node> q = new LinkedList<Node>();public static Queue<Node> q2 = new LinkedList<Node>();public static boolean is_bound(int i, int j) {return i >= 0 && i < N && j >= 0 && j < N;}public static void BFS(int select) {while(!q.isEmpty()) {Node node = q.poll();q2.offer(node);if(select == 1) {if(Map[node.i][node.j] != node.ori_num && Map[node.i][node.j] != 0) {Result = Result < node.depth -1 ? Result : node.depth -1;}}for(int k = 0; k < 4; k++) {int next_i = node.i + d[k][0];int next_j = node.j + d[k][1];if(is_bound(next_i, next_j) && !Visited[next_i][next_j]) {if(select == 0 && Map[next_i][next_j] != 0) {Visited[next_i][next_j] = true;Map[next_i][next_j] = island_num;q.offer(new Node(0, next_i, next_j, 0));}else if(select == 1 && Map[next_i][next_j] != node.ori_num) {Visited[next_i][next_j] = true;q.offer(new Node(node.ori_num, next_i, next_j, node.depth+1));}}}}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);N = sc.nextInt();for(int i = 0; i < N; i++)for(int j = 0; j < N; j++)Map[i][j] = sc.nextInt();for(int i = 0; i < N; i++) {for(int j = 0; j < N; j++) {if(!Visited[i][j] && Map[i][j] != 0) {Visited[i][j] = true;Map[i][j] = island_num; //현재 탐색하는 섬에 번호부여q.offer(new Node(0, i, j, 0));BFS(0);island_num++;}}}while(!q2.isEmpty()) {Node node = q2.poll();Visited[node.i][node.j] = false;}for(int i = 0; i < N; i++) {for(int j = 0; j < N; j++) {if(Map[i][j] != 0) {Visited[i][j] = true;q.offer(new Node(Map[i][j], i, j, 0));BFS(1);}while(!q2.isEmpty()) {Node node = q2.poll();Visited[node.i][node.j]= false;}}}System.out.println(Result);}}cs 반응형'알고리즘 풀이 > BFS(너비 우선 탐색)' 카테고리의 다른 글
BOJ 17141 [연구소 2] (0) 2021.03.04 BOJ 11559 [Puyo Puyo] (4) 2018.10.04 BOJ 1726 [로봇] (0) 2018.10.04 BOJ 2234 [성곽] (0) 2018.10.02 BOJ 1600 [말이 되고픈 원숭이] (3) 2018.09.23