๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
๐ŸŽ› Others.../- ์ž๋ฃŒ๊ตฌ์กฐ & ์•Œ๊ณ ๋ฆฌ์ฆ˜

[์ž๋ฃŒ ๊ตฌ์กฐ] Java๋กœ ๊ทธ๋ž˜ํ”„ ๊ตฌํ˜„ํ•˜๊ธฐ :: ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ๋กœ ๊ตฌํ˜„ํ•œ ๊ทธ๋ž˜ํ”„

by Wonit 2020. 7. 21.

To Do

  • ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ๋ž€?
  • ๊ฐ€์ค‘์น˜๊ฐ€ ์—†๋Š” ๊ทธ๋ž˜ํ”„๋ฅผ ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ๋กœ ๊ตฌํ˜„ํ•˜๊ธฐ
  • ๊ฐ€์ค‘์น˜๊ฐ€ ์žˆ๋Š” ๊ทธ๋ž˜ํ”„๋ฅผ ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ๋กœ ๊ตฌํ˜„ํ•˜๊ธฐ

 

 

์ง€๋‚œ ์‹œ๊ฐ„์— ์šฐ๋ฆฌ๋Š” ์ธ์ ‘ ํ–‰๋ ฌ๋กœ ๊ทธ๋ž˜ํ”„๋ฅผ ๊ทธ๋ฆฌ๋Š” ์‹œ๊ฐ„์„ ๊ฐ€์กŒ๋‹ค.


์˜ค๋Š˜์€ ๊ทธ๋ž˜ํ”„๋ฅผ ๊ทธ๋ฆฌ๋Š” ๋˜ ๋‹ค๋ฅธ ๋ฐฉ๋ฒ•์ธ ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ๋กœ ๊ทธ๋ž˜ํ”„๋ฅผ ๊ทธ๋ ค๋ณด์ž.

์ธ์ ‘ ๋ฆฌ์ŠคํŠธ

Adjancency List ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ๋Š”

 

Geeksforgeeks.org

ํ•œ ๋…ธ๋“œ์— ์—ฐ๊ฒฐ ์ƒํƒœ๋ฅผ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋กœ ๊ตฌํ˜„ํ•œ ๊ฒƒ์„ ์˜๋ฏธํ•œ๋‹ค.

 

์šฐ๋ฆฌ๊ฐ€ ์•„๊นŒ ์œ„์—์„œ ๋งŒ๋“ค์–ด ๋†จ๋˜ ์ž„์˜์˜ ๊ทธ๋ž˜ํ”„๋ฅผ ํ† ๋Œ€๋กœ ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋กœ ๋งŒ๋“ค์–ด๋ณด์ž.

 

๋…ธ๋“œ๊ฐ€ 6๊ฐœ๊ฐ€ ์žˆ์œผ๋ฏ€๋กœ 1๋ฒˆ ๋…ธ๋“œ๋ถ€ํ„ฐ ๊ด€๊ณ„๋ฅผ ์ฐพ์•„๋ณด์ž

 

1 -> 2

2 -> 1 - 3 - 4

3 -> 2 - 4 - 5

4 -> 3 - 5 - 6

5 -> 3 - 4

6 -> 4

 

 

๊ด€๊ณ„๋ฅผ ์ฐพ์•˜์œผ๋‹ˆ ์ด์ œ ๊ฐ ๋…ธ๋“œ์— ํ•ด๋‹นํ•˜๋Š” ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ๋ฅผ ๋งŒ๋“ค์–ด๋ณด์ž.

 

 

์†Œ์Šค ์ฝ”๋“œ

์šฐ๋ฆฌ๋Š” ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ๋ฅผ ์ฃผ๋กœ ๊ทธ๋ž˜ํ”„์—์„œ ๋งŽ์ด ์“ธ ์˜ˆ์ •์ด๋‹ค.

 

๊ทธ๋ž˜ํ”„์—๋Š” ์—ฌ๋Ÿฌ ์ข…๋ฅ˜๊ฐ€ ์žˆ๊ฒ ์ง€๋งŒ ์กฐ๊ธˆ ํฌ๊ฒŒ ๋‚˜๋ˆ„์ž๋ฉด 2๊ฐ€์ง€ ์ข…๋ฅ˜๊ฐ€ ์žˆ๋‹ค.

 

1. ๊ฐ€์ค‘์น˜๊ฐ€ ์—†๋Š” ๊ทธ๋ž˜ํ”„

2. ๊ฐ€์ค‘์น˜๊ฐ€ ์žˆ๋Š” ๊ทธ๋ž˜ํ”„

 

์ด ๋‘ ๋ฒ„์ „ ๋ชจ๋‘ ๊ตฌํ˜„์„ ํ•ด๋ณด๊ฒ ๋‹ค.

 

 

๊ฐ€์ค‘์น˜๊ฐ€ ์—†๋Š” ๊ทธ๋ž˜ํ”„

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

public class Main {

    public static void main(String[] args) throws IOException{
    	// ์ž…์ถœ๋ ฅ ์ฒ˜๋ฆฌ
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = 4 // ์ •์ ์˜ ๊ฐœ์ˆ˜ == ๋…ธ๋“œ ๊ฐฏ์ˆ˜
        int m = 5 // ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜
        
        // ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ
		ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        
        // ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ๋กœ ๊ตฌ์„ฑํ•œ ๊ทธ๋ž˜ํ”„์— ArrayList๋ฅผ ๋„ฃ์–ด์ฃผ๋ฉด์„œ ์ดˆ๊ธฐํ™”
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        
		/** ์ž…๋ ฅ ์˜ˆ์‹œ
        *	1  2
        *   1  3
        *   1  4
        *   2  4
        *   3  4
        */
        for (int i = 0; i < m; i++) {
            String[] nv = br.readLine().split(" ");
            int n1 = Integer.parseInt(nv[0]);
            int n2 = Integer.parseInt(nv[1]);

            graph.get(n1).add(n2);
            graph.get(n2).add(n1);
        }

		1๋ฒˆ ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ์—์„œ 4๋ฒˆ ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ๊นŒ์ง€ ์ถœ๋ ฅ
        for(int i = 1; i <= 4; i++){
        	bw.write(graph.get(i).toString());
        }
        bw.flush();
        bw.close();
    }
}


// ์ถœ๋ ฅ : [2, 3, 4][1, 4][1, 4][1, 2, 3]

 

์ด๋ ‡๊ฒŒ ๊ฐ€์ค‘์น˜๊ฐ€ ์—†๋Š” ๊ทธ๋ž˜ํ”„๋Š” ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ๋ฅผ ํ•˜๋‚˜ ์ƒ์„ฑํ•˜๊ณ  ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜๋งŒํผ ๋ฐ˜๋ณต์„ ๋Œ๋ฉฐ ArrayList ๊ฐ์ฒด ํ• ๋‹น์„ ํ•ด์ค€๋‹ค.

 

๊ทธ๋ฆฌ๊ณ  ๊ฐ„์„ ์˜ ์ˆ˜ ๋งŒํผ ๋ฐ˜๋ณต์„ ๋˜ ๋Œ๋ฉฐ ๊ทธ๋ž˜ํ”„ ์—ฐ๊ฒฐ ์ƒํƒœ๋ฅผ ์ž…๋ ฅ ๋ฐ›๊ณ  ๊ฐ๊ฐ์˜ ๊ทธ๋ž˜ํ”„์— ์ถ”๊ฐ€ํ•ด์ค€๋‹ค.

 

์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œํ’€์ด์—์„œ ์ž์ฃผ ์‚ฌ์šฉ๋˜๋Š” BufferedReader์™€ Writer๋กœ ๊ตฌํ˜„์„ ํ•ด๋ณด์•˜๋‹ค.

 

๊ฐ€์ค‘์น˜๊ฐ€ ์žˆ๋Š” ๊ทธ๋ž˜ํ”„

import java.util.ArrayList;
import java.util.Scanner;

class Edge<W, V> {
    private W weight;
    private V v;

    public void setEdge(W weight, V v) {
        this.weight = weight;
        this.v = v;
    }
}

public class Main {


    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        int n = 4; // ๋…ธ๋“œ์˜ ๊ฐฏ์ˆ˜
        int m = 5; // ๊ฐ„์„ ์˜ ๊ฐฏ์ˆ˜

        ArrayList<Edge<Integer, Integer>> graph = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            graph.add(new Edge<>());
        }

        for (int i = 0; i < m; i++) { // ๊ฐ„์„ ์˜ ๊ฐฏ์ˆ˜๋งŒํผ ๋ฐ˜๋ณต
            int n1 = input.nextInt(); // ๋…ธ๋“œ 1
            int n2 = input.nextInt(); // ๋…ธ๋“œ 2

            int weight = input.nextInt();

            graph.get(n1).setEdge(n2, weight);
            graph.get(n2).setEdge(n1, weight);
        }
    }
}

 

๊ฐ€์ค‘์น˜๊ฐ€ ์žˆ๋Š” ๊ทธ๋ž˜ํ”„์—๋Š” ์šฐ๋ฆฌ์˜ ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ์— ์—ฐ๊ฒฐ๋œ ๊ทธ๋ž˜ํ”„ ๋ฟ๋งŒ ์•„๋‹ˆ๋ผ ๊ทธ์— ๋Œ€ํ•œ ๊ฐ€์ค‘์น˜๋„ ๋„ฃ์–ด์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์— Edge ํด๋ž˜์Šค๋ฅผ ์ƒˆ๋กญ๊ฒŒ ๋งŒ๋“ค์–ด์ค€๋‹ค.

 

๊ทธ Edge ํด๋ž˜์Šค์—๋Š” ๊ฐ€์ค‘์น˜์™€ ๋…ธ๋“œ ๋ฒˆํ˜ธ๊ฐ€ ๋“ค์–ด๊ฐ€๊ฒŒ ๋œ๋‹ค.

 

์ด๋ฒˆ์—๋Š” ์ž๋ฐ”์—์„œ ์ผ๋ฐ˜์ ์œผ๋กœ ๋งŽ์ด ์‚ฌ์šฉ๋˜๋Š” Scanner ๋กœ ์ž…์ถœ๋ ฅ์„ ์ฒ˜๋ฆฌํ•ด๋ณด์•˜๋‹ค.

ํŠน์ง•

 

  ํŠน์ง• ๊ณต๊ฐ„ ๋ณต์žก๋„
์ธ์ ‘ ๋ฆฌ์ŠคํŠธ ํŠน์ • ์ •์ ์— ์ ‘๊ทผํ•˜๋ ค๋ฉด ์—ฐ๊ฒฐ๋œ ๋ชจ๋“  ์ •์  ๋ฐฉ๋ฌธํ•ด์•ผํ•จ v๋ผ๋Š” ๊ฐ„์„ ์˜ ์ˆ˜๋Š” O(V+E)

 

๋Œ“๊ธ€