[코딩테스트] 그래프의 표현

reference : 2021 코딩테스트 기초(최백준) 강의를 공부하며 정리한 내용입니다.

그래프의 표현

• 그래프 저장하는 방법(정점, 간선)
• 정점의 저장 : 개수 v (1~v or 0~(v-1)) ex) {1,2,3,4,5,6}
• 간선 : ex) {(1,2), (1,5), (2,5), (2,3), (3,4), (2,4), (4,5), (4,6)}
• 효율 : 한 정점 v와 연결된 모든 정점을 구하는 시간
  • 인접 행렬 : 2차원 행렬, 배열
  • 인접 리스트 : 리스트 이용, 하나의 정점과 연결되어 있는 모든 정점 저장하는 방식

인접 행렬

• 정점의 개수 V 일때 V x V 크기의 이차원 행렬 이용
• A[i][j] = 1 (i -> j 간선 있을때), 0 (없을 때)
• 공간 : V²
• 효율성 : V
• 장점 : 임의의 두 정점 사이에 간선이 있는지 없는지 쉽게 판단 가능하다. O(1)
• 단점 : 공간을 너무 많이 사용한다. (없는 간선도 저장하기 때문) 그래서 잘 사용 안한다…

인접 리스트

• 리스트를 이용해서 구현. A[i] = i와 연결된 정점을 리스트로 포함함.
• A[1] = 2,5 / A[2] = 1,3,4,5 …
• 공간 : E(간선)
• 효율성 : O(정점의 차수)
• u, v 사이 간선이 있는지 확인 위해선 A[u] 모든 값들을 비교해줘야함. 차수만큼 시간이 걸린다.
• 링크드리스트 이용. C++ vector, Java ArrayList, Python list
• 가중치는 (정점, 가중치) 형태로 같이 저장 ex) A[1] = (2,2) (5,7)

간선 리스트

• C++, java 에서 vector, arraylist 사용할 수 없는데 Linked List 구현의 자신이 없을때 사용하는 방법.
• 배열 이용해 구현.
• 간선을 모두 저장하고 있음. ex) E[0] = 1 2, E[1] = 1 5…
• 각 간선의 앞 정점을 기준으로 개수를 센다, 앞에서 센걸 누적으로 더해줌.
• 효율성 O(차수)

ABCDE (13023번)

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

문제

• 총 N명의 친구 관계가 주어졌을 때 다음과 같은 친구 관계가 존재하는지 구하는 문제
• A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다.

풀이

• 인접 행렬 : 임의의 두 정점 사이에 간선이 있는지 확인 O(1)
• 리스트 : 한 정점과 연결된 모든 간선 O(차수)
• A->B 간선 리스트 다 찾고, C->D 간선 리스트 다 찾고 A->B->C->D->E니까 B->C 가능한지 찾아야 함. 이 때 인접행렬 사용. 있으면 1, 아니면 0
• D->E 인접 리스트 이용해서 찾기.
• 더 쉬운 풀이법 있지만 배운 개념을 다 활용해보기 위해..

import java.util.*;

class Edge{
	int from, to;
	//c++,파이썬과 다르게 임의의 두 수를 묶는게 불가능해서 클래스 만듬
	Edge(int from, int to){
		this.from = from;
		this.to = to;
	}
}

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); //사람 수
		int m = sc.nextInt(); //친구 관계 수
		boolean[][] a = new boolean[n][n]; //인접행렬
		ArrayList<Integer>[] g = (ArrayList<Integer>[]) new ArrayList[n]; //인접리스트
		ArrayList<Edge> edges = new ArrayList<Edge>(); //모든 간선 저장
		for(int i=0; i<n; i++) {
			g[i] = new ArrayList<Integer>(); //인접리스트 사용 위해선 각각 객체 생성시켜줘야함
		}
		for(int i=0; i<m; i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();
			//간선리스트, 양방향이니까 각각 저장
			edges.add(new Edge(from, to));
			edges.add(new Edge(to, from));
			//인접행렬도 양방향 저장
			a[from][to] = a[to][from] = true;
			//인접리스트에도 양방향 저장
			g[from].add(to);
			g[to].add(from);
		}
		m *= 2; //양방향이라 간선 두배
		for(int i=0; i<m; i++) {
			for(int j=0; j<m; j++) {
				int A = edges.get(i).from;
				int B = edges.get(i).to;
				int C = edges.get(j).from;
				int D = edges.get(j).to;
				if(A==B||A==C||A==D||B==C||B==D||C==D) {
					continue; //A,B,C,D 같은 게 있는지 없는지 확인
				}
				if(!a[B][C]) continue; //B->C 간선 있는지 확인
				for(int E : g[D]) { //마지막으로 D->E 확인
					if(A==E||B==E||C==E||D==E) {
						continue;
					}
					System.out.println(1);
					System.exit(0);
				}
			}
		}
		System.out.println(0);
	}
}

-> 처음 배우는 개념이기도 하고… 구현 방법을 처음 봐서 코드 이해하는 것만해도 힘들었다^_ㅜ 내일 문제 풀 수 있겠지..? 하 하 하