글 읽기 - [JAVA] 사용하는 자료구조와 dfs 방법에 대해 질문이 있습니다.

sos0911 5년 전 0

가장 먼저 이 문제를 접했을 때는 A가 B를 신뢰하는 관계를 나타내는 (A, B) 쌍이 input으로 주어지므로

B -> A인 단방향 그래프를 생각하여 하나의 Arraylist 안에 각 노드의 인접 리스트인 LinkedList를 노드의 수만큼 넣어 인접 리스트를 만들고 dfs로 돌리면 되겠다고 생각하고 그대로 구현했는데 시간초과가 났습니다.

도저히 모르겠어서 다른 분들의 코드를 찾아보고 A -> B의 단방향 그래프로 바꾸고 인접 리스트의 자료구조를 이중 Arraylist로 바꾸고 dfs로 어떤 정점을 탐색 시 그 정점이 속해 있었던 인접 리스트의 주인 정점에 대하여 해킹할 수 있는 컴퓨터의 수를 1 증가시키는 방식으로 방식을 바꾸어 진행했더니 그제야 맞았습니다.(첨부한 코드가 맞은 코드입니다.)

질문 드리겠습니다ㅠㅠ

제 딴에는 인접 리스트를 완성할 때 어떤 노드의 인접 리스트를 찾을 때 get()을 써야 하고, 그 리스트에 노드를 추가시킬 때 add()를 써야 하므로 하나의 ArrayList 안에 여러 개의 LinkedList가 들어가는 구조가 맞다고 생각했는데 이 생각이 왜 틀린 걸까요..
변경한 dfs의 방식도 결국 찾아보는 가짓수는 동일한 것 같은데 시간 초과가 왜 똑같이 안 나는 걸까요?

도와주시면 감사하겠습니다.

import java.util.*;
import java.io.*;
public class Main {
    static ArrayList<ArrayList<Integer>> adjlist;
    static int[] visited, nodeval; // 방문 배열, 각 for문에서 초기화 없이 현재 탐색을 시작한 노드 번호 적기
    static int N, M, Cursn; // 현재 탐색하는 노드
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] temp = br.readLine().split(" ");
        N = Integer.parseInt(temp[0]);
        M = Integer.parseInt(temp[1]);
        adjlist = new ArrayList<ArrayList<Integer>>(N+1);
        for(int i = 0; i < N+1; i++)
            adjlist.add(new ArrayList<Integer>()); // 노드 수만큼 인접 리스트 생성(index 1 - N을 사용)
        visited = new int[N+1]; // index 1 - N
        for(int i = 0; i < M; i++){
           temp = br.readLine().split(" ");
        adjlist.get(Integer.parseInt(temp[0])).add(Integer.parseInt(temp[1])); // 단방향 인접 리스트
        }
        nodeval = new int[N+1]; // index 1 - N
        int max = -1; 
        for(int i = 1; i < N+1; i++){
            Cursn = i;
            dfs(i);
        }
        for(int i = 1; i < N+1; i++)
            if(nodeval[i] > max)
                max = nodeval[i];
        StringBuilder sb = new StringBuilder();
        for(int i = 1; i < N+1; i++)
            if(nodeval[i] == max)
                sb.append(i + " ");
        System.out.println(sb.toString());
    }
    static void dfs(int n){
        visited[n] = Cursn;
        for(int i : adjlist.get(n))
            if(visited[i] != Cursn){
                nodeval[i]++;
                dfs(i);
            }
    }
}

sjmsjm1111 5년 전 0

그렇다면 맞은코드인 어레이리스트를 올리시는 것 보다 실패했던 링크드리스트도 올리시는 게 낫지 않을까요

댓글을 작성하려면 로그인해야 합니다.