DFS의 시간복잡도->O(V^2)
정점을 한번씩 들릴것이고 정점에 가서 다른 정정에 갈수있는지를 검사
BFS 너비 우선 탐색
• 큐를 이용해서 지금 위치에서 갈 수 있는 것을 모두 큐에 넣는 방식
• 큐에 넣을 때 방문했다고 체크해야 한다
• 인접 행렬: O(V^2)
• 인접 리스트: O(V+E)
문제 1 )
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
예제 입력 1
4 5 1
1 2
1 3
1 4
2 4
3 4
예제 출력 1
1 2 4 3
1 2 3 4
내가한구현
import java.io.IOException;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
// 함수에서 사용할 변수들
static int[][] graph; // 간선 연결상태
// static boolean[] checked; //확인 여부
static int N; // 정점개수
static int M; // 간선개수
static int start; // 시작정점
public static void DFS(HashSet<Integer> visited, int current_vertex) {
visited.add(current_vertex);
System.out.print(current_vertex + " ");
for (int i = 0; i < graph.length; i++) {
if (graph[current_vertex - 1][i] == 1 && !visited.contains(i + 1)) {
visited.add(i + 1);
DFS(visited,i+1);
}
}
}
public static void BFS() {
HashSet<Integer> visited = new HashSet<>();
Queue<Integer> will_visit = new LinkedList<>();
visited.add(start);
will_visit.add(start);
while (will_visit.isEmpty() == false) {
Integer current_vertex = will_visit.remove();
System.out.print(current_vertex + " ");
for (int i = 0; i < graph.length; i++) {
if (graph[current_vertex - 1][i] == 1 && !visited.contains(i + 1)) {
will_visit.add(i + 1);
visited.add(i + 1);
}
}
}
}
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
start = sc.nextInt();
graph = new int[1001][1001];
int vertex1;
int vertex2;
for (int i = 0; i < M; ++i) {
// st = new StringTokenizer(br.readLine());
vertex1 = sc.nextInt();
vertex2 = sc.nextInt();
graph[vertex1 - 1][vertex2 - 1] = graph[vertex2 - 1][vertex1 - 1] = 1;
}
DFS(new HashSet(), start);
System.out.println();
BFS();
}
}문제 2 ) 연결요소의 개수
문제
방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.
출력
첫째 줄에 연결 요소의 개수를 출력한다.
예제 입력 1
6 5
1 2
2 5
5 1
3 4
4 6
예제 출력 1
2
내가한 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
static StringBuilder builder = new StringBuilder();
public static void DFS(int[][] graph, int start_vertex) {
Stack<Integer> will_visit = new Stack<>();
visited.add(start_vertex);
will_visit.push(start_vertex);
while (will_visit.isEmpty() == false) {
Integer current_vertex = will_visit.pop();
for(int i=1; i<graph.length;i++)
{
if(graph[current_vertex][i]==1&&!visited.contains(i))
{
will_visit.add(i);
visited.add(i);
}
}
}
}
static HashSet<Integer> visited = new HashSet<>();
static int areaCount(int[][] graph, int start_vertex) {
int count = 0;
for (int i=1; i<graph.length;i++)
{
if(!visited.contains(i))
{
DFS(graph,i);
count++;
}
}
return count;
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(tokenizer.nextToken());
int M = Integer.parseInt(tokenizer.nextToken());
int[][] arr = new int[N+1][N+1];
int x, y;
while (M-- > 0) {
tokenizer = new StringTokenizer(reader.readLine());
x = Integer.parseInt(tokenizer.nextToken());
y = Integer.parseInt(tokenizer.nextToken());
arr[x][y] = 1;
arr[y][x] = 1;
}
System.out.println(areaCount(arr,1));
}
}문제 3 ) 이분 그래프
문제
그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.
그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 E(1≤E≤200,000)가 빈 칸을 사이에 두고 순서대로 주어진다. 각 정점에는 1부터 V까지 차례로 번호가 붙어 있다. 이어서 둘째 줄부터 E개의 줄에 걸쳐 간선에 대한 정보가 주어지는데, 각 줄에 인접한 두 정점의 번호가 빈 칸을 사이에 두고 주어진다.
출력
K개의 줄에 걸쳐 입력으로 주어진 그래프가 이분 그래프이면 YES, 아니면 NO를 순서대로 출력한다.
예제 입력 1
2
3 2
1 3
2 3
4 4
1 2
2 3
3 4
4 2
예제 출력 1
YES
NO
package 신규아이디추천;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static boolean dfs(ArrayList<Integer>[] a, int[] color, int x, int c) {
color[x] = c;
for (int y : a[x]) {
if (color[y] == 0) {
if (dfs(a, color, y, 3-c) == false) {
return false;
}
}
else if (color[y] == color[x]) {
return false;
}
}
return true;
}
public static void main(String args[]) throws NumberFormatException, IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(reader.readLine());
StringTokenizer tokenizer;
int V, E;
while (T-- > 0) {
tokenizer = new StringTokenizer(reader.readLine());
V = Integer.parseInt(tokenizer.nextToken());// 정점
E = Integer.parseInt(tokenizer.nextToken());// 간선
ArrayList<Integer>[] a = new ArrayList[V + 1];
for (int i = 1; i <= V; i++)
a[i] = new ArrayList<Integer>();
for (int i = 1; i <= E; i++) {
tokenizer = new StringTokenizer(reader.readLine());
int u = Integer.parseInt(tokenizer.nextToken());
int v = Integer.parseInt(tokenizer.nextToken());
a[u].add(v);
a[v].add(u);
}
int[] color = new int[V+1];
boolean ok = true;
int ans = 0;
for (int i = 1; i <= V; i++) {
if (color[i] == 0) {
if (dfs(a, color, i, 1) == false) {
ok = false;
}
}
}
if(ok == true)
System.out.println("YES");
else
System.out.println("NO");
}
}
}문제 4 ) 토마토
문제
철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
입력
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.
토마토가 하나 이상 있는 경우만 입력으로 주어진다.
출력
여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
예제 입력 1
6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
예제 출력 1
8
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static class Pair {
int x;
int y;
Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
static int[][] a;
public static final int[] dx = { 0, 0, 1, -1 };
public static final int[] dy = { 1, -1, 0, 0 };
public static void main(String args[]) throws NumberFormatException, IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
int m = Integer.parseInt(tokenizer.nextToken());// 가로
int n = Integer.parseInt(tokenizer.nextToken());// 세로
a = new int[n][m];
int[][] dist = new int[n][m];
int check_tomato = 0;
Queue<Pair> q = new LinkedList<Pair>();
for (int i = 0; i < n; i++) {
tokenizer = new StringTokenizer(reader.readLine());
for (int j = 0; j < m; j++) {
a[i][j] = Integer.parseInt(tokenizer.nextToken());
dist[i][j] = -1;// 거리를 -1로 초기화
if (a[i][j] == 1) {
q.add(new Pair(i, j));
dist[i][j] = 0;
}
}
}
while (!q.isEmpty()) {
Pair p = q.remove();
int x = p.x;
int y = p.y;
for (int k = 0; k < 4; k++) { // 인접한 4방향
int nx = x + dx[k];
int ny = y + dy[k];
// 배열의 범위를 벗어나는가
if (0 <= nx && nx < n && 0 <= ny && ny < m) {
if (a[nx][ny] == 0 && dist[nx][ny] == -1) {
q.add(new Pair(nx, ny));
dist[nx][ny] = dist[x][y] + 1;
}
}
}
}
int ans = 0;
//최단 기간
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (ans < dist[i][j]) {
ans = dist[i][j];
}
}
}
//전체가 익지 않은ㄱ 경우 -1
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (a[i][j] == 0 && dist[i][j] == -1) {
ans = -1;
}
}
}
System.out.println(ans);
}
}문제 4 ) 나이트의 이동
문제
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?
입력
입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.
각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.
출력
각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.
예제 입력 1
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1
예제 출력 1
5
28
0
package 신규아이디추천;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static class Pair {
int x;
int y;
Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
static int[][] a;
public static final int[] dx = { 1, 2, -2, -1, -2, -1, 1, 2 };
public static final int[] dy = { 2, 1, 1, 2, -1, -2, -2, -1 };
public static void main(String args[]) throws NumberFormatException, IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(reader.readLine());
StringBuilder builder = new StringBuilder();
StringTokenizer tokenizer;
int[][] dist;
while (T-- > 0) {
int I = Integer.parseInt(reader.readLine()); // 체스판의 한 변의 길이
// 체스판의 크기는 l × l
tokenizer = new StringTokenizer(reader.readLine());
// 나이트가 현재 있는 칸
int current_x = Integer.parseInt(tokenizer.nextToken());
int current_y = Integer.parseInt(tokenizer.nextToken());
tokenizer = new StringTokenizer(reader.readLine());
// 나이트가 이동하려고 하는 칸
int target_x = Integer.parseInt(tokenizer.nextToken());
int target_y = Integer.parseInt(tokenizer.nextToken());
a = new int[I][I];
dist = new int[I][I];
Queue<Pair> q = new LinkedList<Pair>();
q.add(new Pair(current_x, current_y));
dist[current_x][current_y] = 1;
while (!q.isEmpty()) {
Pair p = q.remove();
int x = p.x;
int y = p.y;
if(x==target_x && y==target_y)
{
builder.append((dist[x][y]-1)+"\n");
break;
}
for (int k = 0; k < 8; k++) { // 인접한 4방향
int nx = x + dx[k];
int ny = y + dy[k];
if (0 <= nx && nx < I && 0 <= ny && ny < I) {
if (dist[nx][ny] == 0) {
q.add(new Pair(nx, ny));
dist[nx][ny] = dist[x][y] + 1;
}
}
}
}
}
System.out.println(builder);
}
}