백준공부/java
[백준] 2146번 다리 만들기 (gold 3
gomduri43
2024. 5. 8. 16:48
import java.io.*;
import java.util.*;
class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
class Node {
int x;
int y;
int v;
int num;
public Node(int x, int y, int v, int num) {
this.x = x;
this.y = y;
this.v = v;
this.num = num;
}
}
public class Main {
static int[] numx = {-1, 1, 0, 0};
static int[] numy = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
Queue<Point> que = new LinkedList<>();
PriorityQueue<Node> connect = new PriorityQueue<>(new Comparator<Node>() {
public int compare(Node o1, Node o2) {
return o1.v - o2.v;
}
});
int n = Integer.valueOf(br.readLine());
//맵만들기. true이면 육지
boolean[][] check = new boolean[n + 1][n + 1];
//육지 표시하기.
for (int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= n; j++) {
if (Integer.valueOf(st.nextToken()) == 1) {
//육지표시
check[i][j] = true;
}
}
}
//섬 번호. 순차적으로 섬마다 번호부여하기.
int island = 1;
//같은 섬끼리는 같은 번호로 초기화하기.
int[][] map = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
//육지 존재. 섬마다 번호부여하여 구분하기.
if (check[i][j]) {
map[i][j] = island;
que.clear();
que.offer(new Point(j, i));
connect.offer(new Node(j, i, 0, island));
check[i][j] = false;
while (!que.isEmpty()) {
Point temp = que.poll();
for (int k = 0; k < 4; k++) {
int ty = temp.y + numy[k];
int tx = temp.x + numx[k];
if (tx < 1 || tx > n || ty < 1 || ty > n || !check[ty][tx]) {
continue;
}
map[ty][tx] = island;
check[ty][tx] = false;
que.offer(new Point(tx, ty));
connect.offer(new Node(tx, ty, 0, island));
}
}
island++;
}
}
}
boolean[][][] visit=new boolean[island+1][n+1][n+1];
int answer = 0;
boolean find = false;
//번호로 구분된 섬끼리 연결하면서 도달한 정점이 다른 섬일때 그것이 답.
while (!connect.isEmpty()) {
Node temp = connect.poll();
visit[temp.num][temp.y][temp.x]=true;
for (int k = 0; k < 4; k++) {
int ty = temp.y + numy[k];
int tx = temp.x + numx[k];
//바다로만 이동하면됨. 굳이 같은섬 육지안에서 이동할 필요 x
if (tx < 1 || tx > n || ty < 1 || ty > n || map[ty][tx] == temp.num || visit[temp.num][ty][tx]) {
continue;
}
//바다가 아니고, 시작한 섬과 번호가 다르면 새로운 섬. 즉 다리건설
if (map[ty][tx] > 0 && map[ty][tx] != temp.num) {
answer = temp.v;
find = true;
}
//이동한 걸 각각의 섬마다 구분한여 삼중배열로 구현
else if (map[ty][tx] == 0) {
visit[temp.num][ty][tx]=true;
connect.offer(new Node(tx, ty, temp.v + 1, temp.num));
}
}
if (find) {
break;
}
}
bw.write(answer + "");
bw.flush();
}
}//위의 삼중배열방식으로의 구현은 메모리 측면에서 사실 큰 낭비가 발생한다.
//관점을 바꾸어 보았다. 어떤 정점을 a와 b섬에서 온 다리가 지나려 한다면 a가 지났더라도, b도 지날 수
//있어야 하기에 삼중배열방식으로 구현하였지만
//자세히 생각해보면, a섬 b섬 각각에서 다리를 bfs해나가고, 만약 어떤 정점에서 다음 bfs대상이
//다른 섬번호를 갖고 있다면, 양측에서 해당점점까지 오는데 걸린 거리를 더하면 그 값이
//총 다리의 길이가 될 것이다. 또 이렇게 구현한다면, 삼중배열방식으로 섬마다 방문노드를 체크할 필요가 없다.
//전체 정점을 node( value, islandNum)을 갖는 배열로 구현하여. 각 정점마다 이 노드를 방문한
//섬의 번호와 value를 저장하고서 비교해나가면 된다. 만약 정점이 null값이면 아직 이 곳은 아무도
//오지 못한것이므로 단순히 다리를 연장하면 될 것이고. 이곳이 null이 아니면 누군가 이곳에 왔던 것.
//서로의 islandNum값을 비교해서 서로 다르다면 그 부분에서 다리를 연결하여 두 섬을 잇는 다리를
//만들 수 있을 것이다.
//위에서는 우선순위큐를 이용해서, 거리가 짧은 것부터 우선해서 거리를 구했으므로,
//처음에 나온 값이 무조건 답이다.
//하지만 아래코드는 bfs로 굴리기 때문데, 이보다 짧은 값이 존재가 가능하다. 왜냐하면,
//거리순 정렬이 아니라 들어온 순서부터 초기화 되고 진행되기 때문이다.
//visit노드의 배열의 초기화 측면에서는 처음 섬들의 정점값 부터 진행하므로 상관이 없지만,
//섬들간의 다리 연결에서는 충분히 뒤에 나오는 다리가 더 짧은 가능성이 존재한다.
//따라서, connect 큐가 빌때까지, 그 값들을 비교하여 최솟값을 출력해야한다.import java.io.*;
import java.util.*;
class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
class Node {
int v;
int num;
public Node(int v, int num) {
this.v = v;
this.num = num;
}
}
public class Main {
static int[] numx = {-1, 1, 0, 0};
static int[] numy = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
Queue<Point> que = new LinkedList<>();
Queue<Point> connect=new LinkedList<>();
int n = Integer.valueOf(br.readLine());
//맵만들기. true이면 육지
boolean[][] check = new boolean[n + 1][n + 1];
//육지 표시하기.
for (int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= n; j++) {
if (Integer.valueOf(st.nextToken()) == 1) {
//육지표시
check[i][j] = true;
}
}
}
//섬 번호. 순차적으로 섬마다 번호부여하기.
int island = 1;
//같은 섬끼리는 같은 번호로 초기화하기.
int[][] map = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
//육지 존재. 섬마다 번호부여하여 구분하기.
if (check[i][j]) {
map[i][j] = island;
que.clear();
que.offer(new Point(j, i));
connect.offer(new Point(j,i));
check[i][j] = false;
while (!que.isEmpty()) {
Point temp = que.poll();
for (int k = 0; k < 4; k++) {
int ty = temp.y + numy[k];
int tx = temp.x + numx[k];
if (tx < 1 || tx > n || ty < 1 || ty > n || !check[ty][tx]) {
continue;
}
map[ty][tx] = island;
check[ty][tx] = false;
que.offer(new Point(tx, ty));
connect.offer(new Point(tx, ty));
}
}
island++;
}
}
}
Node[][] visit=new Node[n+1][n+1];
int answer = Integer.MAX_VALUE;
//번호로 구분된 섬끼리 연결하면서 도달한 정점이 다른 섬일때 그것이 답.
while (!connect.isEmpty()) {
Point temp = connect.poll();
if(visit[temp.y][temp.x]==null){
visit[temp.y][temp.x]=new Node(0,map[temp.y][temp.x]);
}
Node node=visit[temp.y][temp.x];
for (int k = 0; k < 4; k++) {
int ty = temp.y + numy[k];
int tx = temp.x + numx[k];
//바다로만 이동하면됨. 굳이 같은섬 육지안에서 이동할 필요 x
if (tx < 1 || tx > n || ty < 1 || ty > n || map[ty][tx]==node.num ) {
continue;
}
//아직 온 게 없는 경우.->방문배열 초기화 및 que에 추가
if(visit[ty][tx]==null){
visit[ty][tx]=new Node(node.v+1, node.num);
connect.offer(new Point(tx, ty));
}
//null이 아니란건 어디선가 이쪽으로 온 정점이 존재하는 것. 이는 해상위일수도.
//바다가 아니고, 시작한 섬과 번호가 다르면 새로운 섬. 즉 다리건설
//한쪽에서 오다가, 다른쪽에서 오던 것과 만나는 케이스. 혹은 한쪽에서 다른쪽으로.
//이 경우 양쪽에서 만들던 다리의 길이를 더하면 연결이됨.
else if(visit[ty][tx].num!=node.num ){
int mid=node.v+visit[ty][tx].v;
answer= answer> mid ? mid : answer;
}
}
}
bw.write(answer==Integer.MAX_VALUE ? "0" : answer+"");
bw.flush();
}
}
결과적으로, 메모리는 1/5가량으로 줄고, 시간도 거의 20%이상 단축 되었다. 코드 길이는 주석의 여부 차이라, 실질적으로. 위 방식은 3559, 아래는 3354바이트이다.