개요 목적
Java BFS 기초 이해와 문제 풀이 해당 글에서는 재귀함수와 BFS기초를 알아보았다.
이번 시간에는 BFS 활용 문제를 풀면서 BFS 문제 풀이 실력을 늘려보자.
동전 교환
3
1 2 5
15
풀이
최소 개수를 구하는 문제이기 때문에, BFS를 사용하는 것이 유리하다.
DFS의 경우, 1,2,5로 시작할 때, 1+1+1+1+1 1에서 1을 더하는 모든 경우의 수를 구한 후에, 값이 나오지 않으면, 2로 넘어가고 5로 넘어간다.
반면에, BFS는 L=1인경우 동전을 하나 사용했을 경우 합을 구한 후에 답이 없다면, L=2 동전 두개 사용한 경우 합을 구하는 방식으로 메소드가 진행된다. 그래서 동전을 3개 사용했을 때, 5+5+5를 구하는 경우의 수를 빠르게 찾을 수 있다.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class 동전교환 {
static int n, m;
static int[] arr;
public static int BFS() {
Queue<Integer> queue = new LinkedList();
for (int i : arr) {
queue.add(i);
}
int L = 1;
//L=1부터 시작 동전 1개만 쓸경우 {1,2,5}
while (!queue.isEmpty()) {
int len = queue.size();
//L=1일 때는 3개만 뽑아서 해야한다.
//L=2인 경우는, 9개
for (int i = 0; i < len; i++) {
Integer cv = queue.poll();
for (int n : arr) {
int nv = cv + n;
if (nv == m) {
return L + 1;
}
queue.add(nv);
}
}
L++;
}
return 0;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
arr = new int[n];
for (int i = 0; i < arr.length; i++) {
arr[i] = sc.nextInt();
}
m = sc.nextInt();
int answer = BFS();
System.out.println(answer);
}
}
미로의 최단거리 통로
0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 0
0 1 0 0 0 1 1 0
1 0 1 1 1 1 0 1
0 0 0 1 0 0 0 1
0 0 1 0 1 0 0 0 0
풀이
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class 미로의최단거리 {
static int[][] board, dis;
static int[] dx={-1, 0, 1, 0};
static int[] dy={0, 1, 0, -1};
static class Point{
public int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void BFS(int x, int y) {
Queue<Point> Q=new LinkedList<>();
Q.offer(new Point(x, y));
board[x][y]=1;
while (!Q.isEmpty()) {
Point tmp = Q.poll();
for (int i = 0; i < 4; i++) {
int nx=tmp.x+dx[i];
int ny=tmp.y+dy[i];
//다음 갈곳이 1보다 크고 7보다 작으며, 지나가지 않은 곳일 때
if(nx>=1 && nx<=7 && ny>=1 && ny<=7 && board[nx][ny]==0){
board[nx][ny]=1; //아에 보드에 이미 간곳이라고 표시해도 괜찮다. 최소의 값을 구하는 것이기 때문에
Q.offer(new Point(nx, ny));
//기존 값에 +1해서 값을 저장한다.
dis[nx][ny]=dis[tmp.x][tmp.y]+1;
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
board=new int[8][8];
dis=new int[8][8];
for(int i=1; i<=7; i++){
for(int j=1; j<=7; j++){
board[i][j]=sc.nextInt();
}
}
BFS(1, 1);
if(dis[7][7]==0) System.out.println(-1);
else System.out.println(dis[7][7]);
}
}
처음 que에 (0,0)이 있을 때는, (1,0) 하고 (0,1) dis 에 0+1한값을 추가하고, que에(1,0)과 (0,1)을 추가한다.
que에 (1,0)(1,0)이 있을 때는, (2,0)과 (0,2) dis에 1+1한 값을 추가하고, que(2,0)과 (0,2)를 추가해서 BFS 계속 진행한다. 이런 방법의 반복으로 (7,7) dis 값을 채운다. que가 empty될 때까지.
토마토
6 4
0 0 -1 0 0 0
0 0 1 0 -1 0
0 0 -1 0 0 0
0 0 0 0 -1 1
풀이
먼저 Q값에 board토마토 상자에 익어 있는 토마토 위치를 넣는다.
이 토마토 위치들을 시작으로 사방으로 다른 토마토를 익히면서, 익혀진 토마토들은 다시 다른 토마토를 익히기 위해 Q에 위치 정보를 넣는다.
Q가 완전히 비어지게 되면, 토마토들의 사방 익힘이 끝난 것을 알 수 있다.
Q가 끝나도 익지 않은 토마토가 있다면 그것은 영원히 익지 않은 토마토인 것이다.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class 토마토 {
static int[] dx={-1, 0, 1, 0};
static int[] dy={0, 1, 0, -1};
static int m, n;
static int[][] board, dis;
static Queue<Point> Q = new LinkedList<>();
static class Point {
public int x, y;
Point(int x, int y){
this.x=x;
this.y=y;
}
}
public static void BFS() {
//Q가 다 빌 때가지 실행하면, Q가 끝나고도 board 토마토 상자 안에 0이 존재하면 영원히 익지 않는 경우다
while (!Q.isEmpty()) {
Point tmp = Q.poll();
for (int i = 0; i < 4; i++) {
int nx = tmp.x+dx[i];
int ny = tmp.y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && board[nx][ny] == 0) {
board[nx][ny] = 1;
dis[nx][ny] = dis[tmp.x][tmp.y] + 1;
//다음 사방향 토마토를 익히게 할 익은 토마토 위치를 Q에 넣는다.
Q.offer(new Point(nx, ny));
}
}
}
}
public static void main(String[] args) {
Scanner kb = new Scanner(System.in);
m=kb.nextInt(); //열
n=kb.nextInt(); //행
board=new int[n][m];
dis=new int[n][m];
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
board[i][j]=kb.nextInt();
//토마토 상자 안을 채울 때, 먼저 익어 있는 토마토 위치를 Q에 넣는다.
//여기서 부터 시작해서, 사방향 익히게할 시작 점이 되고, 익힌 토마토들은 또 Q목록에 넣는다.
if(board[i][j]==1) Q.offer(new Point(i, j));
}
}
boolean flag=true;
int answer=Integer.MIN_VALUE;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(board[i][j]==0) flag=false;
}
}
if(flag){
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
answer=Math.max(answer, dis[i][j]);
}
}
System.out.println(answer);
}
else System.out.println(-1);
}
}
섬 나라 아일랜드
7
1 1 0 0 0 1 0
0 1 1 0 1 1 0
0 1 0 0 0 0 0
0 0 0 1 0 1 1
1 1 0 1 1 0 0
1 0 0 0 1 0 0
1 0 1 0 1 0 0
풀이
import java.util.*;
class Point{
int x, y;
Point(int x, int y){
this.x=x;
this.y=y;
}
}
class Main {
static int answer=0, n;
static int[] dx={-1, -1, 0, 1, 1, 1, 0, -1};
static int[] dy={0, 1, 1, 1, 0, -1, -1, -1};
Queue<Point> queue = new LinkedList<>();
public void BFS(int x, int y, int[][] board){
queue.add(new Point(x, y));
while(!queue.isEmpty()){
Point pos = queue.poll();
for(int i=0; i<8; i++){
int nx=pos.x+dx[i];
int ny=pos.y+dy[i];
if(nx>=0 && nx<n && ny>=0 && ny<n && board[nx][ny]==1){
board[nx][ny]=0;
queue.add(new Point(nx, ny));
}
}
}
}
public void solution(int[][] board){
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(board[i][j]==1){
answer++;
board[i][j]=0;
BFS(i, j, board);
}
}
}
}
public static void main(String[] args){
Main T = new Main();
Scanner kb = new Scanner(System.in);
n=kb.nextInt();
int[][] arr=new int[n][n];
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
arr[i][j]=kb.nextInt();
}
}
T.solution(arr);
System.out.println(answer);
}
}
'자바 자료구조 알고리즘 > DFS & BFS' 카테고리의 다른 글
| 코딩 테스트 Java DFS 활용 문제 풀기 (0) | 2023.05.07 |
|---|---|
| Java 그래프 문제 -인접 행렬, 인접 리스트 ,DFS, BFS (0) | 2023.05.07 |
| Java BFS 기초 이해와 문제 풀이 (0) | 2023.05.07 |
| Java DFS 기초 이해와 문제 풀이 (0) | 2023.05.07 |
