8. 그래프의 표현(하)

View as PDF
Submit solution
Points: 10
Time limit: 1.0s
Java 8 2.0s
Python 2.0s
Memory limit: 64M
Java 8 128M
Python 128M
Author:
jtpark
Problem type

그래프를 표현해 보자. 노드와 간선의 수가 최대 3만일 때는 어떤 표현 방법이 적절한지 생각해 보자.

입력

  • 첫 번째 줄에 그래프의 노드의 수 \(N\)과 간선의 수 \(M\)이 주어진다.\((2 ≤ N ≤ 30000, 1 ≤ M ≤ 30000)\)
  • 두 번째 줄부터 \(M\)개의 줄에 그래프의 간선 정보가 \(a\) \(b\) 형태로 주어진다. 이는 노드 \(a\)와 \(b\)가 양방향으로 연결됨을 나타낸다.\((1 ≤ a ≤ N, 1 ≤ b ≤ N)\)
  • 같은 \(a, b\)쌍은 한 번만 주어지고, 노드는 자기 자신과 연결되어 있지 않다.
  • 하나의 노드에 대한 연결된 노드들의 번호는 오름차순대로 들어온다. 즉 입력의 순서대로 간선 목록에 추가하면, 간선 목록을 따로 정렬할 필요는 없다.

출력

  • \(N\)줄에 걸쳐 \(n\)번째 줄에는 \(n\)번 노드와 연결된 노드들의 번호를 오름차순으로 출력한다.

입력 예시 1

4 3
1 2
1 3
3 4

출력 예시 1

2 3
1
1 4
3

입력 예시 2

3 1
3 1

출력 예시 2

3

1

힌트

  • C언어만으로 동적 배열을 구현하려면 메모리를 직접 할당받아야 하기 때문에 번거롭다. 자체 클래스가 있는 C++, Java, Python으로 하면 비교적 구현이 쉽다.
  • C, C++에서 큰 배열을 main 함수 안에 넣으면 스택 오버플로우의 위험이 있기 때문에 전역으로 선언하는게 좋다. 특히 Visual Studio는 기본 옵션의 스택 할당 크기가 작기 때문에 10000개 정도의 int 배열을 지역으로 선언해도 런타임 에러가 나올 수 있다.

Comments


  • 0
    S20212996  commented on Dec. 15, 2022, 11:59 p.m.

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

    public class Main { public static void main(String[] args) { Scanner s = new Scanner(System.in); int N = s.nextInt(); ArrayList<LinkedList> graph = new ArrayList<LinkedList>(); int M = s.nextInt(); for(int i=0; i<N; i++) graph.add(new LinkedList<Integer>());

      for(int i=0; i<M; i++) {
     int a = s.nextInt()-1;
     int b = s.nextInt()-1;
     graph.get(a).add(b+1);
     graph.get(b).add(a+1);
  }
  for(int i=0; i<graph.size(); i++) {
     for(int j=0; j<graph.get(i).size(); j++) {
        System.out.print(graph.get(i).get(j) + " ");
     }
     System.out.println();
  }

    } }


  • 0
    S20212996  commented on Dec. 15, 2022, 11:58 p.m.

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

    public class Main { public static void main(String[] args) { Scanner s = new Scanner(System.in); int N = s.nextInt(); ArrayList<LinkedList> graph = new ArrayList<LinkedList>(); int M = s.nextInt(); for(int i=0; i<N; i++) graph.add(new LinkedList<Integer>());

      for(int i=0; i<M; i++) {
     int a = s.nextInt()-1;
     int b = s.nextInt()-1;
     graph.get(a).add(b+1);
     graph.get(b).add(a+1);
  }
  for(int i=0; i<graph.size(); i++) {
     for(int j=0; j<graph.get(i).size(); j++) {
        System.out.print(graph.get(i).get(j) + " ");
     }
     System.out.println();
  }

    } }


  • 0
    mskang  commented on Nov. 11, 2020, 11:41 p.m.

    노드의 최대 개수는 3만개 그럼 행렬로 표현했을 때, 3만x3만의 배열이 필요합니다. 배열의 원소 개수는 \(9\times 10^8\)개, 즉 9억개 입니다. 그에 비해 간선의 수는 역시 3만개, 그럼 행렬에 0이 아닌 값을 가지는 원소의 비율을 0.01% 밖에 되지 않습니다. 그럼 그래프를 어떻게 표현해야 할까요? 그리고 이 문제는 실질적인 구현에 있어 발생하는 메모리 문제를 경험할 수 있습니다.