KB IT’s Your Life 4기 - Java 알고리즘 14일차

미로찾기 b2178

⭐️ Queue에 값 추가

q.add(x);
q.offer(x);

add()

해당 큐 맨 뒤에 값 삽입

값 추가 성공 시 true 반환

큐가 꽉 찬 경우 IllegalStateException 에러 발생

offer()

해당 큐 맨 뒤에 값 삽입

값 추가 성공 시 true 반환

값 추가 실패 시 false 반환

package b2178_미로탐색;

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.StringTokenizer;

public class Main {
	static int n, m; // 미로의 개수, 미로의 길이
	static int[][] A;
	static boolean[][] visited;
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());

		A = new int[n][m];
		visited = new boolean[n][m];

		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());
			String line = st.nextToken();
			for (int j = 0; j < m; j++) {
				A[i][j] = Integer.parseInt(line.substring(j, j + 1));
			}
		}

		BFS(0, 0);
		System.out.println(A[n - 1][m - 1]);

	}

	private static void BFS(int i, int j) {
		Queue<int[]> queue = new LinkedList<int[]>();
		queue.add(new int[] { i, j });
		visited[i][j] = true;

		while (!queue.isEmpty()) {
			int[] now_Node = queue.poll();
			System.out.print(now_Node + " ");

			for (int z = 0; z < 4; z++) {
				int x = now_Node[0] + dx[z];
				int y = now_Node[1] + dy[z];

				if (x >= 0 && y >= 0 && x < n && y < m) {
					if (!visited[x][y] && A[x][y] != 0) {
						visited[x][y] = true;
						A[x][y] = A[now_Node[0]][now_Node[1]] + 1;
						queue.add(new int[] { i, j });
					}
				}
			}
		}

	}
}

유니온 파인드

union 연산: 서로 다른 두 개의 집합을 하나의 집합으로 병합하는 연산 (합집합)
find 연산: 하나의 원소가 어떤 집합에 속해있는지를 판단하는 연산

유니온 파인드 - 1차원 배열 이용하기

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
    static int[] parent;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
 
        parent = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }
 
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int command = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
 
            if (command == 0) {
                union(a, b);
            } else if (command == 1) {
                sb.append((isSameParent(a, b) ? "YES" : "NO") + "\n");
            } else {
                continue;
            }
        }
 
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
 
    // x의 부모를 찾는 연산
    public static int find(int x) {
        if (x == parent[x]) {
            return x;
        }
 
        return parent[x] = find(parent[x]);
    }
 
    // y의 부모를 x의 부모로 치환하는 연산 (x > y 일 경우, 반대)
    public static void union(int x, int y) {
        x = find(x);
        y = find(y);
 
        if (x != y) {
            if (x < y) {
                parent[y] = x;
            } else {
                parent[x] = y;
            }
        }
    }
 
    // x와 y의 부모가 같은지 확인
    public static boolean isSameParent(int x, int y) {
        x = find(x);
        y = find(y);
 
        if (x == y) {
            return true;
        }
 
        return false;
    }
 
}

최소 신장 트리

경로가 짧은 것을 찾는 것
가중치의 합이 최소인 것을 찾는 것

크루스칼 알고리즘 : 간건의 가중치 오름차순. 작은순으로 연결 (책에는 이것만)
프림 알고리즘 : 시작 정점 기준, 연결된 정점을 선택

가중치를 구하고, 오름차순함.

package b1197_최소신장트리;

import java.util.*;
import java.io.*;

public class Main {
	static int V, E, sum;
	static int[] parent;
	static PriorityQueue<Edge> pq = new PriorityQueue<Edge>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		V = Integer.parseInt(input[0]);
		E = Integer.parseInt(input[1]);
		for (int i = 0; i < E; i++) {
			input = br.readLine().split(" ");
			int start = Integer.parseInt(input[0]);
			int end = Integer.parseInt(input[1]);
			int weight = Integer.parseInt(input[2]);
			pq.add(new Edge(start, end, weight));
		}
		parent = new int[V + 1];
		for (int i = 1; i <= V; i++)
			parent[i] = i;
		while (!pq.isEmpty()) {
			Edge poll = pq.poll();
			int s = poll.start;
			int e = poll.end;
			int w = poll.weight;

			if (find(s) == find(e))
				continue;
			union(s, e);
			sum += w;
		}
		System.out.println(sum);
	}

	static int find(int x) {
		if (x == parent[x])
			return x;
		parent[x] = find(parent[x]);
		return parent[x];
	}

	static void union(int x, int y) {
		int xRoot = find(x);
		int yRoot = find(y);
		if (xRoot != yRoot)
			parent[yRoot] = x;
	}

	static class Edge implements Comparable<Edge> {
		int start, end;
		int weight;

		public Edge(int start, int end, int weight) {
			this.start = start;
			this.end = end;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			return this.weight - o.weight;
		}
	}
}