04. 그래프 구현하기

그래프란?

그래프는 정점(Vertex)과 그 사이를 잇는 간선(Edge)로 이루어진다.
G = (V, E)는 정점의 집합 V와 간선의 집합 E라고 할 때, 그래프 G는 V와 E의 집합 (V, E)라는 뜻이다.
V(G)는 그래프 G의 정점 집합이고, E(G)는 그래프 G의 간선 집합이다. 간선은 (정점 v, 정점 w)형식이다.

그래프 종류

무방향 그래프

무방향 그래프는 간선에 방향이 없는 그래프를 의미합니다. 하나의 정점이 다른 정점과 방향이 없는 그래프로 이어져 있으면 두 정점이 서로 연결되어 있음을 의미합니다.

방향 그래프

방향 그래프는 간선에 방향이 있는 그래프이다. 무향 그래프와 달리 방향이 있는 간선은 해당 방향으로만 이동할 수 있습니다.

그래프를 표현하는 방법

인접행렬(이중배열)

인접 행렬은 그래프를 가장 쉽게 표현하는 방식으로, 그래프를 정사각형 모양의 2차원 배열로 나타낸다. 2차원 배열의 각 인덱스는 정점을 의미하고, 원소는 각 차원의 인덱스에 해당하는 정점 사이에 간선이 있는지 나타낸다.

인접 리스트(LinkedList)

인접 리스트는 정점이 연결된 정점들을 리스트로 표현하는 방식이다. 이 방식은 원소가 리스트인 1차원 배열로 그래프를 표현할 수 있다.

그래프 관련 문제

순위 - Level.3

import java.util.*;

public class Solution {
	private int countForward(int u, boolean[][] graph, boolean[] isVisited) {
		int count = 1;
		
		for(int v = 0; v < graph[u].length; v++) {
			if(!graph[u][v] || isVisited[v]) continue;
			isVisited[v] = true;
			count += countForward(v, graph, isVisited);
		}
		return count;
	}
	
	private int countBackward(int u, boolean[][] graph, boolean[] isVisited) {
		int count = 1;
		
		for(int v = 0; v<graph.length; v++) {
			if(!graph[v][u] || isVisited[v]) continue;
			isVisited[v] = true;
			count += countBackward(v, graph, isVisited);
		}
		
		return count;
	}
	
	public int solution(int n, int[][] results) {
		
		boolean[][] graph = new boolean[n][n];
		
		for(int[] edge : results) {
			
			int u = edge[0] -1;
			int v = edge[1] -1;
			graph[u][v] = true;
		}
		
		int count = 0;
		for(int u=0; u<n; u++) {
			
			int wins = countForward(u, graph, new boolean[n]) - 1;
			int loses = countBackward(u, graph, new boolean[n])-1;
			if(wins + loses +1 == n) {
				count++;
			}
		}	
	return count;	
	}
}