061 가장 빠른 버스 노선 구하기

• 왜 플로이드 워셜임?

  → 시작점이 주어지지 않았고 모든 정점 쌍 간의 최단 경로 구하는 문제임

  → N이 최대 100임

• “시작 도시와 도착 도시를 연결하는 노선은 1개가 아닐 수 있다” → 중복 간선이 존재하면 최소 비용으로 갱신해야 함

  ⇒ if (distance[s][e] > v) distance[s][e] = v;

  **(3, 5, 1), (3, 5, 10)으로 주어지면 1로 초기화하여 시작한다는 말임~

//처음에 아래 처럼 했다가 예외처리 못해서 틀렸음
distance[i][j] = Integer.MAX_VALUE;
...
if(distance[i][j] > distance[i][k] + distance[k][j])
    distance[i][j] = distance[i][k] + distance[k][j];

⇒distance[i][k] 또는 distance[k][j]가 Integer.MAX_VALUE인 경우, 즉 갈 수 없는 경로인데도 덧셈 연산이 수행되면 오버플로우가 발생함

예: Integer.MAX_VALUE + 5 == 음수 (overflow)

그래서 아래처럼 예외처리 해 주던가

if (distance[i][k] != Integer.MAX_VALUE && distance[k][j] != Integer.MAX_VALUE) {
    if (distance[i][j] > distance[i][k] + distance[k][j]) {
        distance[i][j] = distance[i][k] + distance[k][j];
    }
}

아니면 distance[i][j] = 10000001;처럼 충분히 큰 수로 초기화 **최악의 경우 거리 합이 “100 × 100,000 = 10,000,000”이니까

062 경로 찾기

• 왜 플로이드 워셜인가?

  → N이 100이하에서 눈치까쓰(N^3 쌉 가능)

  → 모즌 정점 쌍에 대해 경로 존재 여부를 알고 싶음

  → 입력도 출력도 0/1 기반 인접 행렬임

• 이 문제에선 경로가 존재하는지 아닌지만 판단하면 됨

  ⇒ S와 E가 모든 중간 경로(K) 중 1개라도 연결되어 있다면 S와 E는 연결 노드로 저장

  for (int k = 0; k < N; k++) {
      for (int i = 0; i < N; i++) {
          for (int j = 0; j < N; j++) {
              if (distance[i][k] == 1 && distance[k][j] == 1)
                  distance[i][j] = 1;
          }
      }
  }
  

063 케빈 베이컨의 6단계 법칙

• 왜 플로이드 워셜?

  → N이 최대 100

  → 모든 정점 쌍의 최단 거리 합임

  **BFS로도 가능하지만 각 정점마다 1회씩 BFS 수행이 필요하므로 좀 더 복잡하다고 함

• 플로이드 워셜로 distance[i][j] = i에서 j까지 최단 거리 모두 구한 후, 모든 i에 대해 distance[i][1] + distance[i][2] + ... + distance[i][N]을 계산해서 가장 작은 값을 가지는 i를 출력하면 끝!

최소 신장 트리

• 그래프의 모든 정점을 연결하면서 사용된 에지들의 가중치의 합이 최소가 되도록 만드는 트리 구조

• 사이클이 없어야 하고 에지의 수는 N-1

• 크루스 칼과 프림 알고리즘이 존재

• 크루스 칼

  1. 에지 리스트 만들기

     • 에지를 "시작 노드, 도착 노드, 가중치" 형태로 저장
     • 인접 리스트나 행렬이 아니라 **에지 중심(edge list)**으로 저장함

  2. 모든 에지을 가중치 기준 오름차순 정렬

  3. 사이클 안 생기게 연결 (유니온 파인드 배열 초기화)

     • 하나씩 에지을 보면서 두 노드를 연결할지 판단
     • 두 노드가 이미 연결되어 있다면(같은 집합이면) → 사이클 생김! 연결하지 않음
     • 아니라면 union 연산으로 연결하고, 가중치를 결과에 더함

     **유니온 파인드가 사이클 판별을 위해 사용함

     <aside>

     • find(x): x가 속한 **집합의 대표(parent)**를 찾음

       → 어떤 노드가 어떤 집합(그룹)에 속하는지를 알려면

       → 그 노드의 최종 대표(root)를 알아야 함

       → 바로 그걸 찾는 게 find(x)의 역할!

     • union(x, y): x와 y가 속한 두 집합을 하나로 합침 </aside>

  4. 에지 개수가 (N - 1)개 되면 종료

• 064 최소 신장 트리 구하기

  • 그냥 MST 구현할 수 있냐 물어보는 문제임

  • 우선순위 큐 써서 자동 정렬해서 하면 됨

  • PriorityQueue는 Comparable이 구현된 객체만 사용 가능

    → 그래서 compareTo() 필수

    <aside>

    주의) 자바에서 PriorityQueue를 쓸 때 Comparable을 구현하거나, Comparator를 넘겨주는 방식 중 하나는 꼭 필요!

    </aside>

• 065 다리 만들기

  1. bfs로 섬마다 번호 붙이기
     • 입력으로 주어진거 2차원 배열로 저장하고 1인 부분을 bfs로 탐색해서 같은 섬은 같은 번호로 바꾸기(2, 3, 4…로)
  2. 각 섬에서 상하좌우로 다리 뻗기
     • 각 칸에서 상하좌우로 뻗어가면서
     • 0(바다)면 킵고잉
     • 같은 섬이면 중단
     • 다른 섬 만났는데 다리 길이가 2이상이면 에지 리스트에 추가
  3. 크루스칼 알고리즘으로
     • 다리 에지 리스트 가중치 기준 정렬(우선순위 큐 사용)
     • 섬 간 최소 가중치 트리 구성(MST!)
     • 모든 섬 연결할 수 없으면 -1

  import java.util.*;
  
  public class P17472_다리만들기 {
  	static int N, M;//지도 세로, 가로 
  	static int[][] map;//지도(0이 바다, 1이 땅)
  	static boolean[][] visited;//섬 구분할 때 방문했는지 체크용
  	static int islandNum = 2; //섬번호 2부터 시작
  	static List<Edge> edgeList = new ArrayList<>();//다리후보목록
  	static int[] parent;//대표 노드
  	
  	//상하좌우 방향 벡터
  	static int[] dx = {-1,1,0,0}; //행 읻ㅇ
  	static int[] dy = {0,0,-1,1};//열 이동 
  
  	public static void main(String[] args) {
  		// TODO Auto-generated method stub
  		Scanner sc = new Scanner(System.in);
  		N=sc.nextInt();
  		M=sc.nextInt();
  		map=new int[N][M];
  		visited = new boolean[N][M];
  		
  		//지도 정보 입력 받고
  		for(int i =0; i< N; i++) {
  			for(int j = 0; j<M; j++)
  				map[i][j] = sc.nextInt();
  		}
  		
  		//bfs로 섬마다 고유 번호 부여
  		for(int i = 0; i<N; i++) {
  			for(int j=0; j<M; j++) {
  				if(!visited[i][j] &&map[i][j] == 1)
  					bfs(i, j, islandNum++);
  			}
  		}
  		
  		//각 섬에서 상하좌우로 다리 연결 가능한지 
  		for(int i =0; i<N; i++) {
  			for(int j = 0; j<M; j++) {
  				if(map[i][j] >= 2)//섬이면
  					findBridge(i, j);
  			}
  		}
  		
  		//MST
  		parent = new int[islandNum]; 
  		for(int i = 2; i< islandNum; i++)
  			parent[i] = i;
  		
  		Collections.sort(edgeList);//다리 가중치 기준 정렬
  		
  		int result = 0;
  		int count = 0; //사용된 다리 개수
  		
  		for(Edge e : edgeList) {
  			if(union(e.from, e.to)){//서로 다른 섬이면 연결 
  				result += e.len;
  				count++;
  			}
  		}
  		
  		//연결된 섬 수가 부족하면 -1
  		if(count == islandNum -3)
  			System.out.println(result);
  		else
  			System.out.println(-1);
  	}
  	
  	//bfs로 섬 구분하고 번호 부여
  	static void bfs(int x, int y, int num) {
  		Queue<int[]> q = new LinkedList<>();
  		q.add(new int[] {x, y});//현재 좌표 {x, y}를 큐에 저장 
  		visited[x][y] = true;
  		map[x][y] = num; //고유 번호 부여
  		
  		while(!q.isEmpty()) {
  			int[] cur = q.poll();//큐에서 현재 좌표 꺼내서 4방향 하나씩 확인 
  			for(int d = 0; d<4; d++) {
  				int nx = cur[0] + dx[d];
  				int ny = cur[1] + dy[d];
  				
  				//다음 좌표 (nx, ny)가 범위 안에 있고 방문 안했고 현재 섬이면(1) 방문 표시하고 큐에 추가 
  				if(inRange(nx, ny)&& !visited[nx][ny] && map[nx][ny] ==1 ) {
  					visited[nx][ny] = true;
  					map[nx][ny] = num;//같은 섬 번호 부여
  					q.add(new int[] {nx, ny});
  				}
  			}
  		}
  	}
  	
  	//범위 체크
  	static boolean inRange(int x, int y) {
  		return x>=0 && y>= 0&& x<N && y< M;
  	}
  	
  	//한 칸에서 상하좌우로 다리 뻗는
  	static void findBridge(int x, int y) {
  		int from = map[x][y];//시작 섬 번호
  		for(int d = 0; d<4; d++) { 
  			int nx = x;
  			int ny = y;
  			int len = 0;//다리 길이
  			
  			//직선으로 쭉
  			while(true) {
  				nx += dx[d];// 다음 칸으로 이동 (행)
  				ny += dy[d];// 다음 칸으로 이동 (열)
  				
  				if(!inRange(nx, ny)) break; //범위밖이면 종료
  				if(map[nx][ny] == from) break; //자기섬이면 종료?
  				if(map[nx][ny] == 0) {//바다면 킵고잉
  					len++;
  				}else {
  					//다른섬 만나면
  					if(len >= 2) {
  						edgeList.add(new Edge(from, map[nx][ny], len));
  					}
  					break;
  				}
  			}
  			
  			
  		}
  	}
  	static int find(int x) {
  		if(parent[x] == x) return x;
  		return parent[x] = find(parent[x]);
  	}
  	
  	static boolean union(int a, int b) {
  		int pa = find(a);
  		int pb = find(b);
  		if(pa == pb) return false;
  		parent[pa] = pb;
  		
  		return true;
  	}
  	
  	static class Edge implements Comparable<Edge>{
  		int from, to, len;
  		
  		Edge(int from, int to, int len) {
              this.from = from;
              this.to = to;
              this.len = len;
          }
  		
  		@Override
          public int compareTo(Edge o) {
              return this.len - o.len; // 오름차순 정렬
          }
  	
  	}
  
  }
  
  

  • 방향 벡터

    static int[] dx = {-1, 1, 0, 0}; // 위, 아래, 좌, 우 static int[] dy = {0, 0, -1, 1};

    d	dx[d]	dy[d]	의미
    0	-1	0	위로 한 칸 (x-1, y)
    1	+1	0	아래로 한 칸 (x+1, y)
    2	0	-1	왼쪽 한 칸 (x, y-1)
    3	0	+1	오른쪽 한 칸 (x, y+1)

    → cur = [2, 3] 일 때

    • d=0일 때 → 위로 이동: nx = 1, ny = 3
    • d=1일 때 → 아래로 이동: nx = 3, ny = 3
    • d=2일 때 → 왼쪽으로 이동: nx = 2, ny = 2
    • d=3일 때 → 오른쪽으로 이동: nx = 2, ny = 4