그래프 표현-1 자바 백준 BOJ 18352, 1325

Java/코딩테스트

그래프 표현-1 자바 백준 BOJ 18352, 1325

sh1mj1 2023. 7. 28. 16:41

그래프는 3가지 구현 방법이 있습니다.

에지 리스트, 인접행렬, 인접 리스트 로 구현할 수 있습니다.

에지 리스트(Edge list)

에지를 중심으로 그래프를 표현합니다. 에지 리스트는 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현합니다. 또는 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현합니다.

가중치 없는 그래프를 에지 리스트로 표현

가중치가 없는 그래프는 출발 노드와 도착 노드만 표현하므로 배열의 행은 2개면 충분합니다.

1에서 2로 뻗어나가는 에지는 [1,2] 로 표현합니다. 이처럼 방향이 있는 그래프는 순서에 맞게 노드를 배열에 저장하는 방식으로 포현합니다. 노드를 배열에 저장하여 에지를 표현하므로 에지 리스트라고 합니다.

가중치 그래프를 에지 리스트로 표현

가중치가 있는 그래프는 행을 3개로 늘려서 3번째 행에 가중치를 저장하면 됩니다.

1 에서 2 로 향하는 가중치가 8 인 에지는 [1, 2, 8] 로 표현합니다. 에지 리스트는 구현하기 쉽습니다. 하지만 특정 노드와 관련 있는 에지를 탐색하는 것이 쉽지 않습니다.

에지 리스트는 벨만 포드 알고리즘(한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘)이나 크루스칼 알고리즘(그래프 내의 모든 정점들을 가장 적은 비용으로 연결하는 알고리즘)에 사용합니다. 노드 중심 알고리즘에는 잘 사용하지 않습니다.

인접 행렬(Adjacency Matrix)

2차원 배열을 자료구조로 이용하여 그래프를 표현합니다. 노드 중심으로 그래프를 표현합니다.

아래는 노드가 5 개인 그래프를 5 ⨉ 5 인접 행렬로 표현한 것입니다.

가중치가 없는 그래프를 인접행렬로 표현

1에서 2를 향하는 에지를 1행 2열에 1을 저장하는 방식으료 표현합니다. 에지가 있다는 표시를 노드 중심으로 한다고 이해하면 됩니다.

인접 행렬로 가중치 있는 그래프 표현

2에서 5로 향하는 가중치를 2행 5열에 기록합니다.

인접행렬을 이용한 그래프 구현은 쉽습니다. 두 노드를 연결하는 에지의 여부 혹은 가중치의 값은 배열에 직접 접근하면 바로 확인할 수 있는 것도 장점입니다.

하지만 노드와 관련되어 있는 에지를 모두 탐색하려면 N 번 접근해야 하므로 노드 개수에 비해서 에지가 적을 때는 공간 효율성이 떨어집니다. 또 노드 개수가 많은 경우에 아예 2차원 배열 선언 자체를 할 수 없는 결함도 있습니다. 따라서 인접 행렬은 노드 개수에 따라 사용 여부를 판단하는 능력도 필요합니다. (노드가 3만개가 넘으면 자바 힙 스페이스 에러(java heap space error) 가 발생합니다.

인접 리스트(adjacency list)

인접 리스트(adjacency list)는 ArrayList 로 그래프를 표현합니다.노드 개수만큼의 ArrayList 를 선언합니다.

가중치 없는 그래프를 인접 리스트로 표현

1과 연결된 2,3 노드는 ArrayList[1] 에 [2, 3] 에 연결하는 방식으로 표현합니다.

가중치 그래프를 인접 리스트로 표현

ArrayList[1] 에 [(2, 8), (3, 3)] 이 연결되어 있습니다. 이는 노드 1과 2가 가중치 8 에지로, 노드 1과 3이 가중치 3 에지로 연결되어 있다는 것을 의미합니다.

다른 그래프 구현 방법에 비해 인접 리스트를 이용한 그래프 구현은 복잡한 편이지만 노드와 연결되어 있는 에지를 탐색하는 시간은 매우 뛰어나며, 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러도 발생하지 않습니다. 그래서 실제 코딩 테스트에서는 인접 리스트를 이용한 그래프 구현을 선호합니다.

백준 18352

https://www.acmicpc.net/problem/18352

18352번: 특정 거리의 도시 찾기

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개

www.acmicpc.net

1. 문제 분석

모든 도로의 거리가 1인 가중치 없는 인접 리스트로 이 그래프를 표현할 수 있습니다. 도시의 개수가 300,000 개, 도로의 최대 크기가 1,000,000 이므로 BFS 탐색을 수행하면 됩니다.

2. 손으로 풀기

1. 인접 리스트로 도시와 도로 데이터의 그래프 구현

2. BFS 탐색으로 각 도시로 가는 최단 거리값을 방문 배열에 저장.

3. 탐색 종료 후 방문 배열에 값이 K 인 도시 출력

3. 슈도코드

도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X
graph: 인접 리스트로 그래프 표현
visited: 방문 배열
qu: BFS 탐색 시 사용할 큐

for(N){ 그래프 초기화 }
for(M){ 그래프에 에지 정보 추가 }

bfsFunc(X)

// bfs 메소드
bfsFunc(int startNode){
   qu 에 시작 노드 넣기
   visitied[현재노드] = 0;
   int depth = 1;
   while(큐가 빌 때까지){
       현재 노드는 큐에서 poll
       for(adjNode: 현재노드의 인접노드){
           adjNode 를 큐에 넣기
           visited[adjNode] = depth;
        }
        depth++
    }
}

4. 코드

public class BaekJun18352 {
    static Queue<Integer> qu = new LinkedList<>();
    static ArrayList<Integer>[] graph;
    static int[] visited;
    static int K;

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

        boolean kExisted = false;
        visited = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            visited[i] = -1;
        }
        graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            graph[start].add(end);
        }

        bfsFunc(X);

        for (int i = 1; i <= N; i++) {
            if (visited[i] == K) {
                kExisted = true;
                sb.append(i).append("\n");
            }
        }
        if (kExisted) {
            System.out.print(sb);
        } else {
            System.out.println(-1);
        }

    }

    static void bfsFunc(int startNode) {
        qu.add(startNode);
        visited[startNode] = 0;
        while (!qu.isEmpty()) {
            int curNode = qu.poll();
            for (int adjNode : graph[curNode]) {
                if (visited[adjNode] == -1) {
                    qu.add(adjNode);
                    visited[adjNode] = visited[curNode] + 1;
                }
            }
        }
    }
}

백준 1325

https://www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한

www.acmicpc.net

1. 문제분석

N 과 M 의 크기가 작은 편이므로 시간 복잡도와 관련된 제약은 크지 않습니다. 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터는 신뢰를 가장 많이 받는 컴퓨터입니다. 그래프의 노드와 에지를 기준으로 이해하면 A 라는 노드에서 탐색 알고리즘으로 방문하는 노드가 B, C 이면 B, C 는 A 에게 신뢰받는 노드가 됩니다.

2. 손으로 풀기

1. 인접 리스트로 컴퓨터와 신뢰 관계 데이터의 그래프를 표현합니다.

2. 모든 노드로 각각 BFS 탐색 알고리즘을 적용해서 탐색을 수행합니다. 탐색을 수행하면서 탐색되는 노드들의 신뢰도를 증가시켜 줍니다.

3. 탐색 종료 후 신뢰도 배열을 탐색햇 신뢰도의 최대값을 Max 로 지정, 신뢰도 배열을 다시 탐색하면서 Max 값을 지니고 있는 노드를 오름차순으로 출력합니다.

신뢰도 배열의 최대값은 3. 3을 가진 인덱스 1, 2 출력.

3. 슈도코드

N: 노드 개수, M: 에지 개수
ans: 정답 배열
graph: 그래프를 인접 리스트로 표현
visited: 방문 배열
for(N){ 그래프에 ArrayList 초기화 }
for(M){ 그래프에 신뢰 관계 저장 }
for(i 을 1 ~ N){
    방문 배열 초기화
    BFS(i) 실행
}
for(N){ answer 배열에서 가장 큰 수 찾기 }
for(N){ answer 배열에서 maxVal 과 같은 값을 가진 index 출력}

//
BFS {
    큐 자료 구조에 출발 노드 더하기(add 연산)
    visited 배열에 현재 노드 방문 기록
    while(큐가 빌 때까지){
        큐에서 poll
        현재 노드의 연결 노드 중에서 방문하지 않는 노드를 큐에 삽입, visited 배열에 방문 기록
        신규 노드 인덱스의 정답 배열 증가시키기
    }
}

4. 코드

public class BaekJun1325Book {

    static int N, M;
    static boolean[] visited;
    static int[] answer;
    static ArrayList<Integer>[] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        graph = new ArrayList[N + 1];
        answer = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            graph[S].add(E);
        }
        for (int i = 1; i <= N; i++) {
            visited = new boolean[N + 1];
            BFS(i);
        }
        int maxVal = 0;
        for (int i = 1; i <= N; i++) {
            maxVal = Math.max(maxVal, answer[i]);
        }
        for (int i = 1; i <= N; i++) {
            if (answer[i] == maxVal) {
                System.out.print(i + " ");
            }
        }
    }
    static void BFS(int index){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(index);
        visited[index] = true;
        while (!queue.isEmpty()) {
            int nowNode = queue.poll();
            for (int i : graph[nowNode]) {
                if (!visited[i]) {
                    visited[i] = true;
                    answer[i]++;
                    queue.add(i);
                }
            }
        }
    }
}

5. 의문점

처음에 접근한 방식은 아래와 같습니다.

슈도 코드

N, M: 컴퓨터 개수, 신뢰 개수
 graph: 인접 리스트,
 visited: 방문 배열
 qu: BFS 을 위한 큐
 visitCnt : 방문한 노드 개수 배열
 visitCntMax: 방문한 노드가 가장 많을 때 노드 수

 for(N){ graph 초기화}
 for(M){ graph 에 신뢰 관계 추가 }

 for(모든 컴퓨터에 대해서){
    bfsFunc(시작노드)
    visitCntMax = Math.max(visitCnt[시작 노드], visitCntMax);
}

// bfs 메소드
bfs(int startNode){
    큐에 시작 노드 넣기
    visitCnt[시작노드] = 0
    while(큐가 빌 때까지){
    	만약 visitCnt[시작노드]가 N-1 이면 함수 종료. (그 이상이 될 수 없음)
        
        큐에서 뽑은 노드를 현재 노드로 설정
        현재 노드 방문 표시
        visitCnt[시작노드]++
        for(adjNode: 현재 노드의 인접 노드){
            만약 방문한 적이 없는 노드라면{
                큐에 인접 노드를 추가
                인접 노드 방문 표시
                visitCnt[시작노드]++
            }
        }
    }
}

코드

public class BaekJun1325 {
    static int N;
    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    static int[] answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        graph = new ArrayList[N + 1];
        answer = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int end = Integer.parseInt(st.nextToken());
            int start = Integer.parseInt(st.nextToken());
            graph[start].add(end);
        }
        int visitCntMax = 0;
        for (int i = 1; i <= N; i++) {
            visited = new boolean[N + 1];
            bfsFunc(i);
            visitCntMax = Math.max(visitCntMax, answer[i]);
        }

        for (int i = 1; i <= N; i++) {
            if (answer[i] == visitCntMax) {
                System.out.print(i + " ");
            }
        }
    }

    static void bfsFunc(int startNode) {
        Queue<Integer> qu = new LinkedList<>();
        qu.offer(startNode);
        visited[startNode] = true;
        while (!qu.isEmpty()) {
            if (answer[startNode] == N - 1) {
                return;
            }
            int curNode = qu.poll();
            for (int adjNode : graph[curNode]) {
                if (!visited[adjNode]) {
                    qu.offer(adjNode);
                    visited[adjNode] = true;
                    answer[startNode]++;
                }
            }
        }
    }
}

그런데 이 방식은 시간초과가 납니다. 위에서 정답으로 작성한 코드와 달리 반복문을 한번 덜 쓰기도 해서 테스트 케이스에 따라 다르겠지만 대체적으로 시간이 덜 걸릴 것이라고 생각했는데 그렇지 않네요...

혹시 이 부분에 대해서 설명해주실 수 있으신 분 계시면 도움 부탁드립니다. (백준 질문 게시판에도 제가 글을 올려놨습니다.https://www.acmicpc.net/board/view/123040 )

'Java > 코딩테스트' 카테고리의 다른 글

유니온 파인드 자바 백준 BOJ 1717, 1976, 1043 (0)	2023.08.05
그래프 표현-2 자바 백준 BOJ 1707, 2251 (0)	2023.08.05
확장 유클리드 호제법 자바 백준 BOJ 21568 Ax+By=C (0)	2023.07.26
유클리드 호제법 -2 자바 백준 BOJ 1033 칵테일 (0)	2023.07.26
유클리드 호제법 -1 자바 백준 BOJ 1934 1850 (0)	2023.07.25

현재글그래프 표현-1 자바 백준 BOJ 18352, 1325

공부하고 작업한 내용을 정리하고 기록하는 블로그

데이터베이스, boj, db, MVC, 스프링, Android, 예외, 오브젝트, 알고리즘, 트랜잭션, 코틀린, 코테, Java, 자바, 백준, kotlin, 안드로이드, 타임리프, 서블릿, 자바 스프링,

Today :
Yesterday :

sh1mj1_log