[Java] 백준. Study 4주차(BFS, DFS)
1. DFS와 BFS
문제
그래프를 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
풀이
dfs(): 재귀로 구현
bfs(): 큐로 구현
코드
272 ms, 23480 KB
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 int n;
static int m;
static int v;
static int[][] array;
static boolean[] visited;
static StringBuilder sb = new StringBuilder();
static void dfs(int start) {
visited[start] = true;
sb.append(start).append(" ");
for(int i=1; i<n+1; i++) {
if(array[start][i]==1 && !visited[i]) {
dfs(i);
}
}
}
static void bfs(int start) {
StringBuilder sb2 = new StringBuilder();
Queue<Integer> qu = new LinkedList<>();
visited = new boolean[n+1];
qu.add(start);
visited[start] = true;
while(!qu.isEmpty()) {
start = qu.poll();
sb2.append(start).append(" ");
for(int i=1; i<n+1; i++) {
if(array[start][i]==1&&!visited[i]) {
visited[i] = true;
qu.add(i);
}
}
}
System.out.println(sb2.toString());
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
v = Integer.parseInt(st.nextToken());
visited = new boolean[n+1];
array = new int[n+1][n+1];
for(int i=0; i<m; i++) {
st = new StringTokenizer(br.readLine());
int row = Integer.parseInt(st.nextToken());
int column = Integer.parseInt(st.nextToken());
array[row][column] = 1;
array[column][row] = 1;
}
dfs(v);
System.out.println(sb.toString());
bfs(v);
}
}
2. 미로 탐색
문제
N×M크기의 배열로 표현되는 미로가 있다.
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
예제 입력 1
4 6
101111
101010
101011
111011
예제 출력 1
15
풀이
거리를 체크할 배열을 미로와 같은 크기를 만든다.
다음으로 이동할 수 있는 상, 하, 좌, 우를 모두 확인해서 만약 미로의 범위를 벗어난다면 무시한다.
범위를 벗어나지 않을 때 미로의 해당 위치 값이 1이라면 거리 값을 현재 위치 + 1로 정해준다.
코드
136 ms, 14688 KB
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 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[][] maze = new int[n][m];
int[][] dist = new int[n][m];
for(int i=0; i<n; i++) {
String s = br.readLine();
for(int k=0; k<m; k++) {
maze[i][k] = s.charAt(k)-'0';
}
}
int[] dx = {0, -1, 0, 1};
int[] dy = {1, 0, -1, 0};
Queue<int[]> qu = new LinkedList<>();
qu.add(new int[]{0, 0});
dist[0][0] = 1;
while(!qu.isEmpty()) {
int[] start = qu.poll();
int x = start[0];
int y = start[1];
for(int i=0; i<4; i++) {
int nextX = x + dx[i];
int nextY = y + dy[i];
if(nextX<0||nextY<0||nextX>=n||nextY>=m) continue;
if(maze[nextX][nextY]==1&&dist[nextX][nextY]==0) {
qu.add(new int[]{nextX, nextY});
dist[nextX][nextY] = dist[x][y] + 1;
}
}
}
System.out.println(dist[n-1][m-1]);
}
}
3. 바이러스
문제
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
출력
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
예제 입력 1
7
6
1 2
2 3
1 5
5 2
5 6
4 7
예제 출력 1
4
풀이
1과 연결되어 있는 컴퓨터의 수를 구하는 문제.
큐를 사용해서 BFS를 구현했다.
코드
124 ms, 14208 KB
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 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int computers = Integer.parseInt(br.readLine());
int pair = Integer.parseInt(br.readLine());
int[][] network = new int[computers+1][computers+1];
for(int i=0; i<pair; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int row = Integer.parseInt(st.nextToken());
int column = Integer.parseInt(st.nextToken());
network[row][column] = 1;
network[column][row] = 1;
}
Queue<Integer> qu = new LinkedList<>();
boolean[] visited = new boolean[computers+1];
qu.add(1);
visited[1] = true;
while(!qu.isEmpty()) {
int start = qu.poll();
for(int i=1; i<=computers; i++) {
if(network[start][i]==1&&!visited[i]) {
qu.add(i);
visited[i] = true;
}
}
}
int answer = 0;
for(int i=2; i< visited.length; i++) {
if(visited[i]) answer++;
}
System.out.println(answer);
}
}
4. 단지 번호 붙이기
문제
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.
출력
첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.
예제 입력 1
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000
예제 출력 1
3
7
8
9
풀이
방문하지 않았으면서 값이 1인 곳부터 탐색을 시작한다.
탐색이 끊기면 총 방문한 집의 수를 return하고, 그 뒤의 지점들 중 다시 탐색을 시작할 지점을 찾는다.
코드
148 ms, 14424 KB
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static boolean[][] visited;
static int[][] house;
static int n;
static int bfs(int[] start) {
int[] dx = {1, -1, 0, 0};
int[] dy = {0, 0, 1, -1};
Queue<int[]> qu = new LinkedList<>();
qu.add(start);
int count = 1;
while(!qu.isEmpty()) {
start = qu.poll();
for(int i=0; i<4; i++) {
int nextX = start[0] + dx[i];
int nextY = start[1] + dy[i];
if(nextX>=0&&nextY>=0&&nextX<n&&nextY<n) {
if(house[nextX][nextY]==1&&!visited[nextX][nextY]) {
qu.add(new int[]{nextX, nextY});
visited[nextX][nextY] = true;
count++;
}
}
}
}
return count;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
house = new int[n][n];
visited = new boolean[n][n];
for(int i=0; i<n; i++) {
String s = br.readLine();
for(int k=0; k<n; k++) {
house[i][k] = s.charAt(k)-'0';
}
}
int count = 0;
ArrayList<Integer> arr = new ArrayList<>();
for(int i=0; i<n; i++) {
for(int k=0; k<n; k++) {
if(house[i][k]==1&&!visited[i][k]) {
visited[i][k] = true;
count++;
arr.add(bfs(new int[]{i, k}));
}
}
}
System.out.println(count);
arr.stream().sorted().forEach(System.out::println);
}
}
5. 촌수계산
문제
우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.
여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.
입력
사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.
각 사람의 부모는 최대 한 명만 주어진다.
출력
입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다.
예제 입력 1
9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6
예제 출력 1
3
풀이
BFS 탐색을 이용했다.
person1을 시작점으로 잡고 person1과 연결되어 있으면 큐에 추가한다.
방문 체크를 할 boolean 배열과 촌수 계산을 할 int 배열도 함께 선언해서 연결되어 있는 지점을 큐에 담을 때 boolean 배열 값은 true로, int 배열 값은 이전 방문 지점의 값 + 1로 넣어준다.
마지막에 person2가 방문한 적이 없으면 -1을, 아니면 int 배열의 person2 값을 출력한다.
코드
120 ms, 14196 KB
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int person1 = Integer.parseInt(st.nextToken());
int person2 = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(br.readLine());
int[][] family = new int[n+1][n+1];
for(int i=0; i<m; i++) {
st = new StringTokenizer(br.readLine());
int parent = Integer.parseInt(st.nextToken());
int child = Integer.parseInt(st.nextToken());
family[parent][child] = 1;
family[child][parent] = 1;
}
boolean[] visited = new boolean[n+1];
int[] depth = new int[n+1];
Queue<Integer> qu = new LinkedList<>();
qu.add(person1);
visited[person1] = true;
int count = 0;
while(!qu.isEmpty()) {
int start = qu.poll();
for(int i=1; i<=n; i++) {
if(family[start][i]==1&&!visited[i]) {
qu.add(i);
visited[i] = true;
depth[i] = depth[start] + 1;
}
}
if(visited[person2]) break;
}
if(!visited[person2]) System.out.println(-1);
else System.out.println(depth[person2]);
}
}
6. 토마토
문제
철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.
창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.
입력
첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.
토마토가 하나 이상 있는 경우만 입력으로 주어진다.
출력
여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.
예제 입력 1
5 3 1
0 -1 0 0 0
-1 -1 0 1 1
0 0 0 1 1
예제 출력 1
-1
풀이
주어진 입력을 3차원 배열로 만든다.
값을 넣으면서 익은 토마토와 총 토마토 개수를 미리 파악하고 값이 1인 경우 큐에 넣는다.
큐가 빌 때까지 아래 작업을 반복한다.
- 큐에서 첫번째 값을 빼서 current 변수에 담는다.
- 다음 좌표를 확인해서 배열의 범위를 벗어나지 않고 배열의 값이 0인 위치를 찾아서 current 값 + 1로 값을 변경해준다.
- 동시에 큐에 담아준다.
- 만약 익은 토마토 수가 전체 토마토 수와 같다면 반복을 중단한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int column = Integer.parseInt(st.nextToken());
int row = Integer.parseInt(st.nextToken());
int floor = Integer.parseInt(st.nextToken());
int total = 0; //총 토마토
int ripe = 0; // 익은 토마토
int[][][] tomato = new int[floor][row][column];
Queue<int[]> queue = new LinkedList<>();
for(int i=0; i<floor; i++) {
for(int k=0; k<row; k++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<column; j++) {
int temp = Integer.parseInt(st.nextToken());
tomato[i][k][j] = temp;
if(temp == 1) {
ripe++;
queue.add(new int[]{i, k, j});
}
else if(temp == 0) total++;
}
}
}
total += ripe;
int[] df = {0, 0, 1, 0, -1, 0};
int[] dr = {0, 0, 0, 1, 0, -1};
int[] dc = {-1, 1, 0, 0, 0, 0};
int days = 0;
while(!queue.isEmpty()) {
int[] start = queue.poll();
int currentFloor = start[0];
int currentRow = start[1];
int currentColumn = start[2];
for(int t=0; t<6; t++) {
int nextFloor = currentFloor + df[t];
int nextRow = currentRow + dr[t];
int nextColumn = currentColumn + dc[t];
if(nextFloor>=0&&nextRow>=0&&nextColumn>=0&&nextFloor<floor&&nextRow<row&&nextColumn<column) {
if(tomato[nextFloor][nextRow][nextColumn]==0) {
queue.add(new int[]{nextFloor, nextRow, nextColumn});
tomato[nextFloor][nextRow][nextColumn] = tomato[currentFloor][currentRow][currentColumn] + 1;
days = tomato[nextFloor][nextRow][nextColumn] - 1;
ripe++;
}
}
}
if(ripe==total) break;
}
if(ripe<total) System.out.println(-1);
else System.out.println(days);
}
}