[백준] 소가 길을 건너간 이유 6 14466 [JAVA]

출처 : www.acmicpc.net/problem/14466

14466번: 소가 길을 건너간 이유 6

문제

소가 길을 건너간 이유는 그냥 길이 많아서이다. 존의 농장에는 길이 너무 많아서, 길을 건너지 않고서는 별로 돌아다닐 수가 없다.

존의 농장에 대대적인 개편이 있었다. 이제 작은 정사각형 목초지가 N×N (2 ≤ N ≤ 100) 격자로 이루어져 있다. 인접한 목초지 사이는 일반적으로 자유롭게 건너갈 수 있지만, 그 중 일부는 길을 건너야 한다. 농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다.

K마리의 (1 ≤ K ≤ 100,K ≤ N2) 소가 존의 농장에 있고, 각 소는 서로 다른 목초지에 있다. 어떤 두 소는 길을 건너지 않으면 만나지 못 할 수 있다. 이런 소가 몇 쌍인지 세어보자.

입력

첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. 그 다음 K줄에는 한 줄의 하나씩 소의 위치가 행과 열로 주어진다.

출력

길을 건너지 않으면 만날 수 없는 소가 몇 쌍인지 출력한다.

풀이

1. 다리를 건너지 않고 연결 될 수 있는 "소" 들을 같은 집합으로 묶기 ( union )

2. parent를 순회하며 다른 집합의 경우, 길을 건너지 않으면 만날 수 없는 소의 쌍으로 간주하여 answer ++ 해주기.

어려웠던 점

Q1. 다리의 연결 유무를 판단하기 위해 어떻게 처리하는게 좋을지?
문제 발생 : 시작점과 끝지점의 다리 유무를 booelan 처리해서 true 로 바꿔주는 방식으로 처음에 진행했다.
ex. input data 의 결과가 아래와 같아진다.  - 아래는 visited 배열을 출력한 것 
4 5 5
2 4 3 4
3 3 3 4
4 3 4 4
3 1 4 1
4 1 4 2
2 2
1 3
3 4
4 4
4 1 

즉, (3,3) - ( 3,4 ) 다리 연결 && (4,3) - (4,4) 다리 연결 
하게 되면 엉뚱하게 (3,4) - ( 4,4) 도 다리 연결 된거로 인식하게 되어서 문제의 요구조건에 충족하지 못하게 된다.

따라서, 1 )- x좌표 y좌표를 이용하기 때문에 ArrayList < Point > [][] 2차원 배열을 N * N 개 생성하기
           2)- 해당 배열에 연결된 다리를 뒤에 붙이기 

Q2. visited 관리를 어떻게 하는게 좋을지? 
   - 3차원 배열 필요 없이 N*N 개의 배열로 처리 하면된다. ( JUST )
   - 어느 한 소가 다리를 건너지 않고 움직일 수 있는 모든 곳은 어차피 같은 집합으로 속하게 되기 때문에 
   - 2번 지나칠 경우의 수 가 없음.

정답 코드

package 알고리즘스터디문제;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 소가길을건너간이유6_코드정리 {

	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, 1, 0, -1 };
	static int N, K, R; // N : map size, K : cows_number , R : road_number
	static int[] parents; // 집합의 유무를 판단할 배열 ( union ) - 처음 들어온 소는 0 번 소라고 의미를 부여.
	static int [][] map; // cows_Exists : 소 있니 ? , bridge : 다리는 있니?
	static boolean[][] visited;
	static ArrayList<Cows> Cows_pos = new ArrayList<>(); // 소 들의 위치를 기억할 곳
	static int answer = 0;
	static ArrayList<Point>[][] road ;
	

	static public class Cows {
		int r;
		int c;
		int number;

		public Cows(int r, int c, int number) {
			super();
			this.r = r;
			this.c = c;
			this.number = number;
		}

	}

	public static void main(String[] args) throws IOException {

		Scanner sc = new Scanner(System.in);
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = sc.nextInt();
		K = sc.nextInt(); // cows_number
		R = sc.nextInt(); // bridge_number

		parents = new int[K + 1];
		map = new int[N][N];
		visited = new boolean[N][N];

		road = new ArrayList[N][N];
		for( int i=0; i<N; i++) {
			for ( int j=0; j<N; j++) {
				
				road[i][j] = new ArrayList<>();
			}
		}
		
		for (int i = 1; i <= K; i++) { // 소의 번호 1부터 시작하도록 하자.
			parents[i] = i;
		}

		// Q. 다리를 어떻게 식별할 수 있을까 ? map 배열을 cows_bridge 객체로 선언
		// input bridge
		for (int i = 0; i < R; i++) {
			int cr = sc.nextInt() -1;
			int cc = sc.nextInt() -1;
			int nr = sc.nextInt() -1;
			int nc = sc.nextInt() -1;
			road[cr][cc].add(new Point(nr,nc));
			road[nr][nc].add(new Point(cr,cc));
		}
		// input cows pos
		for (int i = 1; i <= K; i++) {
			int r = sc.nextInt() - 1;
			int c = sc.nextInt() - 1;
			map[r][c] = i;
			Cows_pos.add(new Cows(r, c, i)); // 소 있는 위치 기억하기 그리고 번호도

		}
		// 1. 다리 건너지 않고 연결될 수 있는 녀석들 연결하기 => 그래서 parent 로 집합 만들자.
		// 1-1) visit 배열은 [N][N] 한가지로 해도 될듯 , 어차피 한번 지나간 거리는 모두 연결되는 집합에 속하게 된다.
		// 따라서, 또 다시 지나갈 필요가 없음.
		for (int i = 0; i < K; i++) {
			Cows cur_cow = Cows_pos.get(i);
			if (!visited[cur_cow.r][cur_cow.c]) { // 방문하지 않은 곳이라면
				visited[cur_cow.r][cur_cow.c] = true; // 방문처리하고
				makeset(cur_cow); // bfs 시작
			}
		}
		// 2. parent를 순회하며 같은 부모가 아닌 녀석들을 한 쌍으로 두고 count 하나씩 증가하기
		for (int i = 1; i <= K - 1; i++) {
			for (int j = i + 1; j <= K; j++) {
				if (parents[i] != parents[j]) { // 같은 집합이 아니라면
					answer++;
				}
			}
		}
		System.out.println(answer);
	}

	private static void print() {
		// TODO Auto-generated method stub
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}

	private static void makeset(Cows cow) {
		// 1. 다리 건너지 않고 연결될 수 있는 녀석들 연결하기 => 그래서 parent 로 집합 만들자.
		// 1-1) visit 배열은 [N][N] 한가지로 해도 될듯 , 어차피 한번 지나간 거리는 모두 연결되는 집합에 속하게 된다.
		// 따라서, 또 다시 지나갈 필요가 없음.
		Queue<Cows> queue = new LinkedList<>();
		queue.add(new Cows(cow.r, cow.c, cow.number)); // 해당 소의 위치와 번호를 큐에 넣고
		int cn = cow.number; // 현재 소의 번호

		while (!queue.isEmpty()) { // bfs gogo
			Cows cur_cow = queue.poll();
			// 길을 제외한 4방 서치를 통해 다른 소를 만나면, 그 소 번호와 시작 소 번호의 부모가 다르면 합쳐주기
			int cr = cur_cow.r; // 현재 소의 행
			int cc = cur_cow.c; // 현재 소의 열

			for (int d = 0; d < 4; d++) {
				int nr = cr + dr[d]; // next row
				int nc = cc + dc[d]; // next column

				// 다음으로 갈 곳이 맵 안에 위치하고 방문하지 않았다면 gogo 그리고 다리가 연결되어 있지 않다면
				if (isIn(nr, nc) && !visited[nr][nc] && notBridge(cr, cc, nr, nc)) {
					// 방문처리하고
					visited[nr][nc] = true;
					// 큐에 넣고
					queue.add(new Cows(nr, nc, cn)); // 소의 번호는 처음 시작한 녀석으로 퉁쳐도 될듯 어차피 같은 집합으로 속하잖아.

					int nn = map[nr][nc]; // next cow number
					// 다음 소의 위치에 다른 소가 있고 그녀석의 부모가 다르다면 합쳐주자
					if (nn != 0 && nn != cn && parent(nn) != parent(cn)) {
						union(nn, cn); // 다음 소 랑, 현재 소랑 같은 집합으로 두기
					}
				}
			}

		}

	}

	// 시간 초과뜨면 레벨링 고려해보기
	private static void union(int nn, int cn) {
		// TODO Auto-generated method stub
		int px = parent(nn);
		int py = parent(cn);

		parents[px] = py; // py를 px에 합치자.
	}

	private static int parent(int nn) {
		// TODO Auto-generated method stub
		if (nn == parents[nn])
			return nn;
		else {
			int P = parent(parents[nn]);
			return P;
		}
	}

	private static boolean notBridge(int cr, int cc, int nr, int nc) {
		// cr, cc 는 현재 위치 = nr nc 는 다음에 위치
		// 연결된 다리가 없다는 뜻
		if ( road[cr][cc].isEmpty()) return true;
		for( int i=0; i< road[cr][cc].size(); i++) {
			if ( road[cr][cc].get(i).x == nr && road[cr][cc].get(i).y == nc) {
				return false;
			}
			
		}
		
		return true;
	}

	private static boolean isIn(int nr, int nc) {

		if (nr >= 0 && nr < N && nc >= 0 && nc < N)
			return true;
		return false;
	}
}

 

실패했던 코드

package 알고리즘스터디문제;

/*
 * 3 3 3 4
 * 4 3 4 4 
 * 이렇게 다리 연결하면
 * 3 4 -> 4 4 못가는 걸로 되서 에러! 
 * 
 */
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 소가길을건너간이유6_14466 {

	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, 1, 0, -1 };
	static int N, K, R; // N : map size, K : cows_number , R : road_number
	static int[] parents; // 집합의 유무를 판단할 배열 ( union ) - 처음 들어온 소는 0 번 소라고 의미를 부여.
	static cows_bridge[][] map; // cows_Exists : 소 있니 ? , bridge : 다리는 있니?
	static boolean[][] visited;
	static ArrayList<Cows> Cows_pos = new ArrayList<>(); // 소 들의 위치를 기억할 곳
	static int answer = 0;

	// cows_Exists : 소 있니 ? , bridge : 다리는 있니?
	static public class cows_bridge {
		int cows_number; // 여기에 소가 있는 번호
		boolean bridge; // 다리가 연결 되어 있니?

		public cows_bridge(int cows_number, boolean bridge) {
			this.cows_number = cows_number;
			this.bridge = bridge;
		}

	}

	static public class Cows {
		int r;
		int c;
		int number;

		public Cows(int r, int c, int number) {
			super();
			this.r = r;
			this.c = c;
			this.number = number;
		}

	}

	public static void main(String[] args) throws IOException {

		Scanner sc = new Scanner(System.in);
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = sc.nextInt();
		K = sc.nextInt(); // cows_number
		R = sc.nextInt(); // bridge_number

		parents = new int[K + 1];
		map = new cows_bridge[N][N];
		visited = new boolean[N][N];

		for (int i = 1; i <= N; i++) { // 소의 번호 1부터 시작하도록 하자.
			parents[i] = i;
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = new cows_bridge(0, false);
			}
		}

		// Q. 다리를 어떻게 식별할 수 있을까 ? map 배열을 cows_bridge 객체로 선언
		// input bridge
		for (int i = 0; i < R; i++) {
			map[sc.nextInt() - 1][sc.nextInt() - 1].bridge = true;
			map[sc.nextInt() - 1][sc.nextInt() - 1].bridge = true;
		}
		// input cows pos
		for (int i = 1; i <= K; i++) {
			int r = sc.nextInt() - 1;
			int c = sc.nextInt() - 1;
			map[r][c].cows_number = i;
			Cows_pos.add(new Cows(r, c, i)); // 소 있는 위치 기억하기 그리고 번호도

		}
		// 1. 다리 건너지 않고 연결될 수 있는 녀석들 연결하기 => 그래서 parent 로 집합 만들자.
		// 1-1) visit 배열은 [N][N] 한가지로 해도 될듯 , 어차피 한번 지나간 거리는 모두 연결되는 집합에 속하게 된다.
		// 따라서, 또 다시 지나갈 필요가 없음.
		for (int i = 0; i < K; i++) {
			Cows cur_cow = Cows_pos.get(i);
			if (!visited[cur_cow.r][cur_cow.c]) { // 방문하지 않은 곳이라면
				visited[cur_cow.r][cur_cow.c] = true; // 방문처리하고
				makeset(cur_cow); // bfs 시작
			}
		}
		for (int i = 1; i <= K; i++) {
			System.out.print(i + " ");
		}
		System.out.println();
		for (int i = 1; i <= K; i++) {
			System.out.print(parents[i] + " ");
		}
		System.out.println();
		print();
		// 2. parent를 순회하며 같은 부모가 아닌 녀석들을 한 쌍으로 두고 count 하나씩 증가하기
		for (int i = 1; i <= K - 1; i++) {
			for (int j = i + 1; j <= K; j++) {
				if (parents[i] != parents[j]) { // 같은 집합이 아니라면
					answer++;
				}
			}
		}
		System.out.println();
		System.out.println(answer);
	}

	private static void print() {
		// TODO Auto-generated method stub
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(map[i][j].bridge + " ");
			}
			System.out.println();
		}
	}

	private static void makeset(Cows cow) {
		// 1. 다리 건너지 않고 연결될 수 있는 녀석들 연결하기 => 그래서 parent 로 집합 만들자.
		// 1-1) visit 배열은 [N][N] 한가지로 해도 될듯 , 어차피 한번 지나간 거리는 모두 연결되는 집합에 속하게 된다.
		// 따라서, 또 다시 지나갈 필요가 없음.
		Queue<Cows> queue = new LinkedList<>();
		queue.add(new Cows(cow.r, cow.c, cow.number)); // 해당 소의 위치와 번호를 큐에 넣고
		int cn = cow.number; // 현재 소의 번호

		while (!queue.isEmpty()) { // bfs gogo
			Cows cur_cow = queue.poll();
			// 길을 제외한 4방 서치를 통해 다른 소를 만나면, 그 소 번호와 시작 소 번호의 부모가 다르면 합쳐주기
			int cr = cur_cow.r; // 현재 소의 행
			int cc = cur_cow.c; // 현재 소의 열

			for (int d = 0; d < 4; d++) {
				int nr = cr + dr[d]; // next row
				int nc = cc + dc[d]; // next column

				// 다음으로 갈 곳이 맵 안에 위치하고 방문하지 않았다면 gogo 그리고 다리가 연결되어 있지 않다면
				if (isIn(nr, nc) && !visited[nr][nc] && notBridge(cr, cc, nr, nc)) {
					// 방문처리하고
					visited[nr][nc] = true;
					// 큐에 넣고
					queue.add(new Cows(nr, nc, cn)); // 소의 번호는 처음 시작한 녀석으로 퉁쳐도 될듯 어차피 같은 집합으로 속하잖아.

					int nn = map[nr][nc].cows_number; // next cow number
					// 다음 소의 위치에 다른 소가 있고 그녀석의 부모가 다르다면 합쳐주자
					if (nn != 0 && nn != cn && parent(nn) != parent(cn)) {
						System.out.println("current number : " + cn + " next number :" + nn);
						union(nn, cn); // 다음 소 랑, 현재 소랑 같은 집합으로 두기
					}
				}
			}

		}

	}

	// 시간 초과뜨면 레벨링 고려해보기
	private static void union(int nn, int cn) {
		// TODO Auto-generated method stub
		int px = parent(nn);
		int py = parent(cn);

		parents[px] = py; // py를 px에 합치자.
	}

	private static int parent(int nn) {
		// TODO Auto-generated method stub
		if (nn == parents[nn])
			return nn;
		else {
			int P = parent(parents[nn]);
			return P;
		}
	}

	private static boolean notBridge(int cr, int cc, int nr, int nc) {
		// cr, cc 는 현재 위치 = nr nc 는 다음에 위치
		// map[cr][cc]에 도 다리가 있고, map[nr][nc]에도 다리가 있으면 두개는 연결된 것이다.
		if (map[cr][cc].bridge && map[nr][nc].bridge) {
			return false;
		}

		return true;
	}

	private static boolean isIn(int nr, int nc) {

		if (nr >= 0 && nr < N && nc >= 0 && nc < N)
			return true;
		return false;
	}
}