[Java] 그래프 기본 템플릿

 

 

DFS

package study.blog.codingnojam;

public class Study_DFS_Recursion {

	// 방문처리에 사용 할 배열선언
	static boolean[] vistied = new boolean[9];
	
	// 그림예시 그래프의 연결상태를 2차원 배열로 표현
	static int[][] graph = {{}, {2,3,8}, {1,6,8}, {1,5}, {5,7}, {3,4,7}, {2}, {4,5}, {1,2}};
	
	public static void main(String[] args) {
		dfs(1);
	}
	
	static void dfs(int nodeIndex) {
		// 방문 처리
		vistied[nodeIndex] = true;
		
		// 방문 노드 출력
		System.out.print(nodeIndex + " -> ");
		
		// 방문한 노드에 인접한 노드 찾기
		for (int node : graph[nodeIndex]) {
			// 인접한 노드가 방문한 적이 없다면 DFS 수행
			if(!vistied[node]) {
				dfs(node);
			}
		}
	}
}

 

 

 

 

BFS

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class B_16234 {

	static int N, L, R;
	static int[][] board, new_board;
	static boolean[][] visit;
	static int[] dy = new int[] { -1, 0, 1, 0 };
	static int[] dx = new int[] { 0, 1, 0, -1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		L = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());

		board = new int[N][N];
		new_board = new int[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		int t = 0;
		while (true) {

			visit = new boolean[N][N];
			boolean check = false;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (visit[i][j])
						continue;
					if (bfs(i, j) > 1) {
						check = true;
					}
				}
			}
			if (!check)// 연합한 국가들이 없었다면
			{
				break;
			}
			for (int i = 0; i < N; i++) {
				board[i] = new_board[i].clone();
			}

			t += 1;
		}
		System.out.println(t);

	}

	static int bfs(int sy, int sx) {

		Queue<int[]> queue = new ArrayDeque<>(); // bfs를 위한 queue
		Queue<int[]> queue2 = new ArrayDeque<>(); // 나라 상태 변화를 위한 queue - 인구 이동할 나라들을 담을 queue
		queue.offer(new int[] { sy, sx });
		queue2.offer(new int[] { sy, sx });
		visit[sy][sx] = true;

		int sumPeople = 0;
		int countryCnt = 0;

		while (!queue.isEmpty()) {
			int[] now = queue.poll();
			int ny = now[0];
			int nx = now[1];

			sumPeople += board[ny][nx];
			countryCnt += 1;

			for (int i = 0; i < 4; i++) {
				int yy = ny + dy[i];
				int xx = nx + dx[i];

				if (yy < 0 || yy > N - 1 || xx < 0 || xx > N - 1)
					continue;
				if (visit[yy][xx])
					continue;

				int gap = Math.abs(board[ny][nx] - board[yy][xx]);

				if (gap >= L && gap <= R) {
					visit[yy][xx] = true;
					queue.offer(new int[] { yy, xx });
					queue2.offer(new int[] { yy, xx });
				}
			}
		}

		// 연합할 국가들이 없다면 기존의 값 담아줌.
		if (countryCnt == 1) {

			new_board[sy][sx] = board[sy][sx];

		} else if (countryCnt > 1) { // 연합할 국가들이 있다면 new_board에 값 담아줌

			int movePeople = sumPeople / countryCnt;
			while (!queue2.isEmpty()) {
				int[] now = queue2.poll();

				new_board[now[0]][now[1]] = movePeople;

			}

		}
		return countryCnt;
	}
}

 

 

 

Dijkstra

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

// (틀림 51%) 출발지에서 목적지로 갈 수 없는 경우에 대한 언급은 없지만
// 그럴 경우가 있으므로 그럴 땐 0을 출력해줘야 함.
public class B_13905 {

	static int houseCnt, bridgeCnt, startPoint, endPoint;
	static List<List<Node>> houseList;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		houseCnt = Integer.parseInt(st.nextToken());
		bridgeCnt = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine());
		startPoint = Integer.parseInt(st.nextToken());
		endPoint = Integer.parseInt(st.nextToken());

		houseList = new ArrayList<>();
		for (int i = 0; i < houseCnt + 1; i++) {
			houseList.add(new ArrayList<>()); // 0 dummy
		}

		for (int i = 0; i < bridgeCnt; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());

			houseList.get(s).add(new Node(e, c));
			houseList.get(e).add(new Node(s, c));
		}

		System.out.println(dijkstra());
	}

	static int dijkstra() {
		boolean[] visit = new boolean[houseCnt + 1]; // 0 dummy

		Queue<Node> pqueue = new PriorityQueue<>((n1, n2) -> n2.c - n1.c);

		pqueue.offer(new Node(startPoint, 0));

		int result = Integer.MAX_VALUE;
		while (!pqueue.isEmpty()) {
			Node current = pqueue.poll();
			if (visit[current.e])
				continue;
			visit[current.e] = true;

			if (current.c != 0)
				result = Math.min(result, current.c);
			if (current.e == endPoint)
				return result;
			for (Node next : houseList.get(current.e)) {
				if (visit[next.e])
					continue;
				pqueue.offer(next);
			}
		}
		return 0;
	}

	static class Node {
		int e;
		int c;

		public Node(int e, int c) {
			super();
			this.e = e;
			this.c = c;
		}

		@Override
		public String toString() {
			return "Node [e=" + e + ", c=" + c + "]";
		}

	}
}

 

 

 

 

Prim

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class B_1389 {

	static int N, M;
	static List<List<Integer>> connection;
	static int baconCnt = Integer.MAX_VALUE, answer;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		connection = new ArrayList<>();
		for (int i = 0; i < N + 1; i++) {
			connection.add(new ArrayList<>());
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			connection.get(s).add(e);
			connection.get(e).add(s);

		}

		for (int i = 1; i < N + 1; i++) {
			int s = check(i);
			if (baconCnt > s) {
				baconCnt = s;
				answer = i;
			}
		}
		System.out.println(answer);
	}

	static int check(int start) {
		Queue<int[]> queue = new ArrayDeque<>();
		queue.add(new int[] { start, 0 });
		boolean[] visited = new boolean[N + 1];
		int sum = 0;

		while (!queue.isEmpty()) {
			int[] now = queue.poll();
			int nowNode = now[0];
			int nowCnt = now[1];

			if (visited[nowNode])
				continue;

			visited[nowNode] = true;
			sum += nowCnt;

			for (int next : connection.get(nowNode)) {
				if (visited[next])
					continue;
				queue.offer(new int[] { next, nowCnt + 1 });

			}

		}
		return sum;
	}

}

 

 

 

 

 

참고

https://codingnojam.tistory.com/44