Algorithm, BFS 문제
BFS 사용 특징
- 가장빠른길을 찾을 수 있다
- 다녀간 길을 체크해줘야한다
bfs 1차원 문제
문제 1.
- 항상 2차원 배열만 풀다가 1차원 배열의 문제를 보니 낯설었다.
- 글 풀이
수빈 3 동생 1
1회
0 1 2 3 4 5 6 7 8 9....
0 0 1 0 1 0 1 0 0 0.....
3 -> 2, 4, 6으로 갈수있다
2회
0 1 2 3 4 5 6 7 8 9...12
0 2 1 2 1 2 1 2 2 0...2
2 -> 1, 6으로 갈수있다
4 -> 5, 8으로 갈수있다
6 -> 7, 12로 갈수있다
2에서 3으로도 갈수있지만 이미 0초일때
방문했고, 최단시간을 구하는 것이므로
방문할필요가없다.
만약 방문한다고 하면 무한루프에 빠질수있다 3->2->3->2....
구현코드
package org.baekjoon;
import java.util.*;
public class test1697_hideSeek {
static Queue<Integer> q; // 다음 회에 들어갈 위치
static int road[]; // road[i] = j i위치에 j시간이 걸린다
static int dongsang;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int subin = sc.nextInt();
dongsang = sc.nextInt();
if(subin == dongsang)
System.out.println("0");
else {
road = new int[100001];
q = new LinkedList<>();
q.add(subin);
bfs();
}
}
public static void bfs() {
while(!q.isEmpty()) {
int current = q.poll();
int[] move = {current-1 , current+1, current*2};
// 3가지 방법으로 움직일수있다.
for(int i=0; i<3; i++) {
int next = move[i];
// 범위를 벗어날수없다
if(next < 0 || next >= 100001)
continue;
// 이미 다녀간적이 있다면 나간다
if(road[next] != 0)
continue;
// 현재위치에서 다음으로 1회 이동했으므로, 다음 위치 이동수 = 현재까지 이동수+1
road[next] = road[current]+1;
if(next == dongsang) {
System.out.println(road[next]);
return;
}
q.add(next);
}
}
}
}
문제 2/
- 숨바꼭질2
- 핵심 : 큐에서 꺼낼때 방문확인을 하여 같은 시간에는 중복허용
package org.baekjoon;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class test12851_hideSeek2 {
static Queue<Integer> q; // 다음 회에 들어갈 위치
static int road[]; // road[i] = j i위치에 j시간이 걸린다
static boolean visited[]; // road[i] = j i위치에 j시간이 걸린다
static int dongsang, subin;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
subin = sc.nextInt();
dongsang = sc.nextInt();
if (subin != dongsang) {
road = new int[100001];
visited = new boolean[100001];
q = new LinkedList<>();
q.add(subin);
bfs();
} else
System.out.println(0 + "\n" + 1);
}
static int count = 0;
public static void bfs() {
int time = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int s = 0; s < size; s++) {
int current = q.poll();
int[] move = { current - 1, current + 1, current * 2 };
// 큐에 입력할때 방문확인하지 않고 꺼낼때 확인
visited[current] = true;
// 3가지 방법으로 움직일수있다.
for (int i = 0; i < 3; i++) {
int next = move[i];
// 범위를 벗어날수없고, 방문한곳은 못들어간다
if (next >= 0 && next < 100001 && visited[next] == false) {
q.add(next);
if (next == dongsang) {
count++;
}
}
}
}
time++;
// 최소시간일때 도착하면 처음 count가 0보다 커지니까 그 이상의 시간은 볼필요없으므로 종료
if(count > 0)
break;
}
System.out.println();
System.out.println(time + "\n" + count);
}
}
문제 3.
package org.baekjoon;
import java.io.*;
import java.util.*;
public class test2178_miro {
static int[][] map;
static int[][] way;
static int n,m;
static Queue<dot3> q;
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());
map = new int[n][m];
way = new int[n][m];
for(int i=0; i<n; i++) {
String line = br.readLine();
for(int j=0; j<m; j++) {
map[i][j] = Integer.parseInt(line.charAt(j)+"");
}
}
//Arrays.fill(way,200);
q = new LinkedList<>();
way[0][0] = 1;
q.add(new dot3(0,0));
bfs();
System.out.println(way[n-1][m-1]);
}
static int[] dx = {0,0,1,-1};
static int[] dy = {1,-1,0,0};
private static void bfs() {
while (!q.isEmpty()) {
dot3 dot = q.poll();
// 4방향으로 움직일 수 있다.
for(int i=0; i<4; i++) {
int x = dot.x + dx[i];
int y = dot.y + dy[i];
if(x < 0 || x >= n || y < 0 || y >= m)
continue;
// 못가는 길 or 이미 지나간길
if(map[x][y] == 0 || way[x][y] != 0)
continue;
way[x][y] = way[dot.x][dot.y]+1;
q.add(new dot3(x,y));
}
}
}
}
class dot3{
int x;
int y;
dot3(int x, int y){
this.x = x;
this.y = y;
}
}