KB IT's Your Life/알고리즘
[02] 재귀, 그래프(graph), 미로찾기
지식보부상님
2025. 5. 9. 09:36
✅ 실전 그래프 활용 - 인접 리스트 (list)
위의 그래프를 다음과 같이 인접 리스트(ArrayList)로 저장
List<List<Integer>> graph = new ArrayList<>() {{
add(List.of(1, 3, 6));
add(List.of(0, 3));
add(List.of(3));
add(List.of(0, 1, 2, 7));
add(List.of(5));
add(List.of(4, 6, 7));
add(List.of(0, 5));
add(List.of(3, 5));
}};
◈ 그래프의 간선(edge) 정보가 주어질 때
(예시)
edges = [[0, 1], [0, 3], [0, 6], [1, 3], [2, 3], [3, 7], [4, 5], [5, 6], [5, 7]]
n = 8 # 노드의 개수위처럼 그래프의 간선 정보가 주어지면 다음과 같이 인접 리스트를 저장하면 된다.
List<List<Integer>> graph = new ArrayList<>();
// 그래프 초기화
// n : vertex 개수
for(int i = 0 ; i < n ; i++) {
graph.add(new ArrayList<>());
}
// 간선 정보 저장
for(int edge[] : edges){
int x = edge[0];
int y = edge[1];
// 양방향 그래프
graph.get(x).add(y); // x -> y 연결
graph.get(y).add(x); // y -> x 연결
}
◈ 다음 노드 탐색
for(int nextVertex : graph.get(curVertex)){ ... }✅ 실전 그래프 활용 - 인접 리스트 (dict)
위와 같은 그래프 주어졌을 때 해쉬맵(HashMap)으로 저장
Map<Integer, List<Integer>> graph = new HashMap<>() {{
put(0, List.of(1, 3, 6));
put(1, List.of(0, 3));
put(2, List.of(3));
put(3, List.of(0, 1, 2, 7));
put(4, List.of(5));
put(5, List.of(4, 6, 7));
put(6, List.of(0, 5));
put(7, List.of(3, 5));
}};
◈ 그래프의 간선(edge) 정보가 주어질 때
(예시)
edges = [[0, 1], [0, 3], [0, 6], [1, 3], [2, 3], [3, 7], [4, 5], [5, 6], [5, 7]]
n = 8 # 노드의 개수위처럼 그래프의 간선 정보가 주어지면 다음과 같이 인접 리스트를 저장하면 된다.
Map<Integer, List<Integer>> graph = new HashMap<>();
// 인접 리스트 초기화
for(int i = 0; i < n ; i++) {
graph.put(i, new ArrayList<>());
}
// 간선 추가
for( int[] edge : edges) {
int x = edge[0];
int y = edge[1];
// 양방향 그래프
graph.get(x).add(y); // x -> y
graph.get(y).add(x); // y -> x 연결
}
◈ 다음 노드 탐색
for(int nextVertex : graph.get(curVertex)){ ... }
✅ 실전 그래프 활용 - 인접 행렬
위와 같은 그래프 주어졌을 때 인접 행렬로 그래프 정보 저장
int[][] graph = {
{0, 1, 0, 1, 0, 0, 1, 0},
{1, 0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 0},
{1, 1, 1, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 1, 0, 1, 1},
{1, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 1, 0, 1, 0, 0}
};
◈ 인접 행렬을 인접 리스트로 변환
int[][] graph = {
{0, 1, 0, 1, 0, 0, 1, 0},
{1, 0, 0, 1, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 0},
{1, 1, 1, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 1, 0, 1, 1},
{1, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 1, 0, 1, 0, 0}
};
// 인접 행렬 초기화
List<List<Integer>> adjList = new ArrayList<>();
int n = graph.length;
for(int i = 0 ; i < n ; i++ ){
adjList.add(i, new ArrayList<>());
for(int j = 0 ; j < n ; j++ ) {
if(graph[i][j] == 1) {
adjList.get(i).add(j); // i -> j 연결
}
}
}✅ DFS 구현
◈ visited를 set으로 구현한 경우
public void dfs(List<List<Integer>> graph, Set<Integer> visited, int curVertex){
visited.add(curVertex);
for( int nextVertex : graph.get(curVertex)){
if(!visited.contains(nextVertex){
dfs(graph, visited, nextVertex);
}
}
}
public void solve(List<List<Integer>> graph){
Set<Integer> visited = HashMap<>();
dfs(graph, visited, 0);
}
◈ visited를 array로 구현한 경우
public void dfs(List<List<Integer>> graph, boolean[] visited, int curVertex){
visited[curVertex] = true;
for( int nextVertex : graph.get(curVertex){
if(!visited[nextVertex]){
dfs(graph, visited, nextVertex);
}
}
}
public void solution(List<List<Integer>> graph){
final int N = graph.size();
boolean[] visited = new boolean[N];
dfs(graph, visited, 0);
}✅ BFS 구현
◈ visited를 set으로 구현
public void bfs(List<List<Integer>> graph, int startVertex){
Queue<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.add(startVertex);
visited.add(startVertex);
while(!queue.isEmpty()){
int curVertex = queue.remove();
for( int nextVertex : graph.get(curVertex) {
if(!visited.contains(nextVertex)){
queue.add(nextVertex);
visited.add(nextVertex);
}
}
}
}
public void solution(List<List<Integer>> graph) {
bfs(graph, 0);
}
◈ visited를 array로 구현
public void bfs(List<List<Integer>> graph, int startVertex){
Queue<Integer> queue = new LinkedList<>();
final int N = graph.size();
boolean[] visited = new boolean[N];
queue.add(startVertex);
visited[startVertex] = true;
while(!queue.isEmpty()){
int curVertex = queue.remove();
for( int nextVertex : graph.get(curVertex)){
if(!visited[nextVertex]){
queue.add(nextVertex);
visited[nextVertex] = true;
}
}
}
}
public void solution(List<List<Integer>> graph){
bfs(graph, 0);
}✅ DFS & BFS 를 이용한 네트워크 개수 찾기
◈ 네트워크란?
- 서로 연결된 노드들의 집합
- 즉 연결된 덩어리
- dfs / bfs를 실행하면 하나의 네트워크를 탐색한 것
◈ 예제
// 인접 리스트로 그래프 표현
Map<Integer, List<Integer>> graph = new HashMap<>() {{
put(0, List.of(1, 3));
put(1, List.of(0, 3, 5));
put(2, List.of(4));
put(3, List.of(0, 1));
put(4, List.of(2));
put(5, List.of(1));
}};위와 같이 저장된 graph는 다음과 같이 연결되어 있다
[네트워크 1]
0
/ \
1 - 3
|
5
[네트워크 2]
2 - 4
네트워크의 개수를 찾는 코드
public int countNetworks(Map<Integer, List<Integer>> graph) {
Set<Integer> visited = new ArrayList<>();
int count = 0;
for( int curVertex : graph.keySet()) {
if(!visited.contains(curVertex)) {
dfs(graph, visited, curVertex);
count++;
}
}
return count;
}
💻<예제>
더보기
✅ 문제 파악
- 서로 연결된 네트워크의 개수 구하기
- 매개변수
- computers : 인접 행렬로 주어지는 그래프
- n : 컴퓨터의 개수
✅ 접근 방법
- 네트워크의 개수는 bfs / dfs 로 그래프를 탐색하여 구할 수 있다.
✅ 코드 구현
import java.util.*;
class Solution {
public int solution(int n, int[][] computers) {
int answer = 0;
final int N = computers.length;
Map<Integer, List<Integer>> adjList = new HashMap<>();
Set<Integer> visited = new HashSet<>();
// 인접 행렬을 인접 리스트로 변환
for(int i = 0 ; i < N ; i++) {
adjList.put(i, new ArrayList<>());
for(int j = 0 ; j < N ; j++) {
if(computers[i][j] == 1 && i != j) {
adjList.get(i).add(j);
}
}
}
// 네트워크 찾기
for( int curVertex : adjList.keySet()) {
if(!visited.contains(curVertex)){
bfs(adjList, visited, curVertex);
answer++;
}
}
return answer;
}
public void bfs(Map<Integer, List<Integer>> graph, Set<Integer> visited, int curVertex) {
visited.add(curVertex);
for (int nextVertex : graph.get(curVertex)) {
if (!visited.contains(nextVertex)) {
bfs(graph, visited, nextVertex);
}
}
}
}
더보기
✅ 문제 파악
- 리턴
- 전체 방을 모두 방문할 수 있으면 true, 아니면 false 리턴
- 변수
- roooms : rooms[i] 에는 i번 방 이후에 방문할 수 있는 방이 저장되어 있음
✅ 접근 방법
- 방을 vertex, 주어진 키를 edge 라고 생각하여 그래프로 해석
- 모두 방문 가능한지는 dfs / bfs 를 이용하여 확인 가능
✅ 코드 구현
import java.util.*;
class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
final int N = rooms.size();
boolean[] visited = new boolean[N];
dfs(rooms, visited, 0);
for(boolean room : visited) {
if(!room)
return false;
}
return true;
}
public void dfs(List<List<Integer>> rooms, boolean[] visited, int curRoom) {
visited[curRoom] = true;
for(int nextRoom : rooms.get(curRoom)) {
if(!visited[nextRoom]) {
dfs(rooms, visited, nextRoom);
}
}
}
}
더보기
✅ 문제 파악
- 1~n 까지의 노드
- 리턴
- leaf 노드 중 가장 먼 노드의 개수 구하기
- 변수
- n : 노드의 개수
- edge : edge[i] 에는 두 노드 [x, y] 가 저장되어 있음
✅ 접근 방법
- bfs 이용하여 각 노드의 depth 를 visited의 key 로 저장
- 주의❗ edge에는 1~n 까지의 노드가 저장되어있으므로, 자체적으로 0~n-1 번의 노드로 바꾸어 저장
✅ 코드 구현
import java.util.*;
class Solution {
public int solution(int n, int[][] edge) {
int answer = 0;
// 그래프 초기화
List<List<Integer>> graph = new ArrayList<>();
for(int i = 0 ; i < n ; i++) {
graph.add(new ArrayList<>());
}
// 인접 리스트로 저장
for(int[] e : edge) {
int x = e[0]-1;
int y = e[1]-1;
graph.get(x).add(y);
graph.get(y).add(x);
}
// bfs로 그래프 탐색
answer = bfs(graph, 0);
return answer;
}
public int bfs(List<List<Integer>> graph, int startNode) {
Queue<Integer> queue = new LinkedList<>();
// visited의 key: Node 번호, value: 그래프의 depth
Map<Integer, Integer> visited = new HashMap<>();
queue.add(startNode);
visited.put(startNode, 1);
while(!queue.isEmpty()) {
int curNode = queue.remove();
for(int nextNode : graph.get(curNode)) {
if(!visited.containsKey(nextNode)) {
queue.add(nextNode);
visited.put(nextNode, visited.get(curNode)+1);
}
}
}
// depth 가 최대인 것의 개수 구하기
int maxValue = 0;
int count = 0;
for(int key : visited.keySet()){
if(maxValue < visited.get(key)) {
maxValue = visited.get(key);
count = 1;
} else if(maxValue == visited.get(key)) {
count++;
}
}
return count;
}
}✅ 배우게 된 점 (피드백)
- visited에 각 노드의 depth 를 저장할 필요 없이 bfs 탐색시에 maxValue 와 count 를 세면 시간을 줄일 수 있다.
더보기
✅ 문제 파악
- 변수
- coins : 가진 동전의 종류
- amount : 도달해야 할 값
- 리턴
- amount 에 도달가능하면 만들 수 있는 동전의 최소의 개수를 리턴
- 도달 불가능하면 -1 을 리턴
✅ 접근 방법
- 첫 접근
- while문으로 큰 금액 동전부터 사용하도록 했음
- ⇒ ❌ 큰 금액의 동전을 사용하지 않고도 amount 에 도달가능한 경우가 발생
- dfs 이용
- 0 ~ amount 가 그래프의 노드라고 생각
- visited[i] : i 원에 도달했음을 의미
- 큐에는 현재 남은 금액과 낸 동전의 개수를 저장
✅ 코드 구현
import java.util.*;
class Solution {
public int coinChange(int[] coins, int amount) {
int count = -1;
if(amount == 0) {
return 0;
}
Queue<int[]> queue = new LinkedList<>();
boolean[] visited = new boolean[amount+1];
visited[amount] = true;
queue.add(new int[]{amount, 0});
while(!queue.isEmpty()) {
int[] cur = queue.remove();
int curRemaining = cur[0];
int coinCount = cur[1];
if(curRemaining == 0) {
return coinCount;
}
for(int coin : coins) {
int next = curRemaining-coin;
if(next >=0 && !visited[next]){
queue.add(new int[]{next, coinCount+1});
visited[next] = true;
}
}
}
return count;
}
}
더보기
✅ 문제 파악
- 변수
- graph : graph[i] 에는 노드 i 와 연결된 노드가 저장되어있음
- 리턴
- bipartite이면 true, 아니면 false를 리턴
✅ 접근 방법
- 노드 x 에 대해 연결된 노드 y 는 서로 다른 집합으로 분류
- visited[i] 가 1 이거나 -1 인 집합으로 분류
- visited[x] = -visited[y]
- 노드 x 와 y 가 연결되어 있는데, visited 집합이 동일한 집합으로 분류되면 false 리턴
✅ 코드 구현
import java.util.*;
class Solution {
public boolean isBipartite(int[][] graph) {
Queue<Integer> queue = new LinkedList<>();
final int n = graph.length;
int[] visited = new int[n];
for(int i = 0 ; i < n ; i++ ) {
if(visited[i] == 0) {
queue.add(i);
visited[i] = 1;
while(!queue.isEmpty()) {
int cur = queue.remove();
for(int next : graph[cur]) {
if(visited[next] == 0) {
visited[next] = -visited[cur];
queue.add(next);
} else if(visited[next] == visited[cur]){
return false;
}
}
}
}
}
return true;
}
}