글 읽기 - 두 개의 코드 차이점이 뭔가요..?

le_effort 3년 전 0

96-110 (구글링 통해 얻은 코드)

111-123 (제가 직접 쓴 코드)

구글링을 통해 얻은 코드로 제출하면 정답이 되는데

제가 직접 쓴 코드는 길이 값이 잘 안나오더라구요

왜 잘못나오는지 알려주실수 있나요..?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
	static int n,m;
	static int ans = 0;
	static int map[][];
	static boolean visited[][];
	static int island_num=1;
	static int dx[] = {0,0,1,-1};
	static int dy[] = {1,-1,0,0};
	static int parent[];
	static PriorityQueue<Edge>pq = new PriorityQueue<>();
	static Queue<Node>q = new LinkedList<>();
	static int connect = 0;
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        m = Integer.parseInt(t[1]);
        map = new int[n][m];
        visited = new boolean[n][m];
        for(int i=0; i<n; i++) {
        	String[] tt = br.readLine().split(" ");
        	for(int j=0; j<m; j++) {
        		map[i][j] = Integer.parseInt(tt[j]);
        		if(map[i][j]==1) {
        			map[i][j]=-1;
        		}
        	}
        }
        
        for(int i=0; i<n; i++) {
        	for(int j=0; j<m; j++) {
        		if(map[i][j]==-1) {
        			map[i][j]=island_num;
        			dfs(i,j,island_num);
        			island_num++;
        		}
        	}
        }
        parent = new int[island_num];
        for(int i=1; i<island_num; i++) {
        	parent[i] = i;
        }
        while(!q.isEmpty()) {
        	Node a = q.poll();
        	for(int i=0; i<4; i++) {
        		get_bridge(a.x,a.y,i, a.num);
        	}
        }
        
        while(!pq.isEmpty()) {
        	Edge a = pq.poll();
        	if(a.len >1 && check(a.v1,a.v2)) {
        		merge(a.v1,a.v2);
        		ans+=a.len;
        		connect++;
        	}
        }
        if(connect != island_num-2) {
        	System.out.println(-1);
        }
        else {
        	System.out.println(ans);
        }
	}
	public static void merge(int a, int b) {
		int rootA = find(a);
		int rootB = find(b);
		if(a>b) {
			int tmp = rootA;
			rootA= rootB;
			rootB= tmp;
		}
		parent[rootB]=rootA;
	}
	public static int find(int x) {
		if(parent[x]==x) {
			return x;
		}
		parent[x] = find(parent[x]);
		return parent[x];
	}
	public static boolean check(int x, int y) {
		x = find(x);
		y = find(y);
		if(x==y) {
			return false;
		}
		return true;
	}
	
	public static void get_bridge(int x, int y, int d, int num) {
		int nx = x+dx[d];
		int ny = y+dy[d];
		int len =0;
		while(nx>=0 && nx<n && ny>=0 && ny<m && map[nx][ny]!=num) {
			if(map[nx][ny]!=0) {
				System.out.println(len);
				pq.add(new Edge(num,map[nx][ny],len));
				return ;
			}
			nx+=dx[d];
			ny+=dy[d];
			len++;
		}
	}
//	public static void get_bridge(int x, int y, int d, int num) {
//		int cnt = 0;
//		while(isRange(x+dx[d],y+dy[d]) && map[x+dx[d]][y+dy[d]]!=num) {
//			cnt++;
//			x+=dx[d];
//			y+=dy[d];
//			if(map[x][y]!=0 && map[x][y]!=num) {
//				pq.add(new Edge(num,map[x][y],cnt));
//				System.out.println(cnt);
//				break;
//			}
//		}
//	}
	public static void dfs(int x, int y, int num) {
		q.add(new Node(x,y,num));
		for(int i=0; i<4; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			if(isRange(nx,ny) && map[nx][ny]==-1) {
				map[nx][ny]=num;
				dfs(nx,ny,num);
			}
		}
	}
	public static boolean isRange(int x, int y) {
		if(x>=0 && y>=0 && x<n && y<m) {
			return true;
		}
		return false;
	}
}
class Edge implements Comparable<Edge>{
	int v1,v2,len;
	Edge(int  v1, int v2, int len){
		this.v1=v1;
		this.v2=v2;
		this.len=len;
	}
	public int compareTo(Edge o) {
		return this.len-o.len;
	}
}
class Node{
	int x,y,num;
	Node(int x, int y, int num){
		this.x=x;
		this.y=y;
		this.num=num;
	}
}

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

문제

문제

출처

ICPC

두 개의 코드 차이점이 뭔가요..?

le_effort 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말