728x90
반응형
[알고리즘] 너비 우선 탐색(BFS: Breadth First Search, 백준 2178, 1697, 12851, 1012 -Java)
알고리즘 공부를 계속 미루는 제 자신을 보고 이대로는 안되겠다 싶어 😇
본격적으로 코딩테스트를 준비(+알고리즘 공부) 해보려고 합니다.
물론 혼자하면 작심삼일이 될거 같아
무료 Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의
강의 커리큘럼에 맞춰 공부해보자!!
[무료] Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의
IT기업 코딩테스트 대비를 위한 [자료구조 및 알고리즘 핵심이론 & 관련 실전 문제 풀이 강의] 입니다. - JAVA 편 -, - 강의 소개 | 인프런
www.inflearn.com
너비 우선 탐색(BFS)
그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발하여 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘 입니다.
시간 복잡도는 O(V+E) 입니다.(V: 노드 수, E: 엣지 수)
완전 탐색 이란?
가능한 모든 경우의 수를 다 확인해서 정답을 찾는 방법입니다.
예를 들어 🔒자물쇠 비밀번호가 3자리로 구성되어 있다고 하면
반드시 풀 수 있는 방법은 000부터 999까지 모두 시도해보는 것 입니다.!🔓
너비 우선 탐색은 선입선출(FIFO) 방식으로 탐색하기 때문에, 큐를 이용하여 구현합니다.
또한, 시작 노드와 가까운 노드를 우선하여 탐색하기 때문에!!!!!!
목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장합니다.
BFS 핵심 원리
방문했던 노드는 다시 방문하지 않습니다.
따라서 방문한 노드를 체크하기 위한 배열이 따로 필요합니다.
(위 2가지 사항은 DFS도 동일합니다.^^)
그래프를 인접 리스트로 표현하는 거 역시 DFS와 동일합니다.
차이점이 있다면 stack이 아니라 queue를 사용한다는 점 입니다.
그림으로 표현하면 다음과 같습니다.
백준 2178
2178번: 미로 탐색BFS는 depth를 다 탐색하고 그다음 depth로 넘어갑니다.
따라서 BFS를 사용하면 최단경로를 구할 수 있습니다.
(저는 스스로 해결하지 못했습니다. ㅠㅠ, 큐를 이용하는 것은 알았으나 큐에 x, y를 저장하는 방법을 몰라서 해맸습니다….)
풀이
public class Quiz2178 {
static int n = 0;
static int m = 0;
public static void main(String[] args) throws IOException {
/**
* (1,1)에서 출발해서 (n, m)으로 이동할때 최단 거리
*/
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
// 미로 저장
int[][] miro = new int[n][m];
for(int i = 0; i < n; i++) {
String str = br.readLine();
char[] chars = str.toCharArray();
for(int j = 0; j < chars.length; j++) {
int data = chars[j];
miro[i][j] = data - '0';
}
}
// 방문 이력 배열
boolean[][] visited = new boolean[n][m];
bfs(miro, visited, 0, 0);
System.out.print(miro[n-1][m-1]);
}
private static void bfs(int[][] miro, boolean[][] visited, int start, int end) {
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(start, end));
visited[start][end] = true;
int[] upAndDown = {1, -1, 0, 0};
int[] leftAndRight = {0, 0, 1, -1};
while (!queue.isEmpty()) {
Node node = queue.poll();
for (int i = 0; i < 4; i++) {
// 새로운 탐색 좌표
int newX = node.getX() + upAndDown[i];
int newY = node.getY() + leftAndRight[i];
// 탐색 범위를 벗어난 경우
if (newX < 0 || newY < 0 || newX >= n || newY >= m) {
continue;
}
// 방문한 이력이 없고, 탐색 가능한 곳이면 dfs 탐색
if (!visited[newX][newY] && miro[newX][newY] == 1) {
queue.add(new Node(newX, newY));
visited[newX][newY] = true;
// 새로 탐색한 곳에 1씩 더하여 depth를 저장
miro[newX][newY] = miro[node.getX()][node.getY()] + 1;
}
}
}
}
static class Node {
private int x;
private int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
}
}백준
1697번: 숨바꼭질
이 문제의 핵심은 visited[]를 통해 방문 이력을 검사하고, depth를 기록하는 것입니다.
수빈이가 동생을 찾을 수 있는 가장 빠른 시간(depth)만 알면 되기 때문에 visted[]의 중복을 허용하지 않습니다.
(수빈이를 3명 만들어서 동생을 먼저 찾은 수빈이의 시간(depth)를 출력하면 됩니다.)
풀이
public class Quiz1697 {
static int result = 0;
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 k = Integer.parseInt(st.nextToken());
// 수빈이가 동생보다 앞에 있으면 뒤로만 갈 수 있음
// 뒤로 1칸 이동 1초 소요
if(n >= k) {
System.out.print(n-k);
br.close();
return;
}
// 방문 이력 배열(깊이도 같이 표시)
// n의 범위가 0 ~ 100_000 -> 100_001개
int[] visited = new int[100_001];
bfs(visited, n, k);
System.out.print(result);
br.close();
}
private static void bfs(int[] visited, int n, int k) {
Queue<Integer> queue = new ArrayDeque<>();
// 수빈이의 위치 큐에 삽입
queue.add(n);
// 수빈이의 위치 방문 표시
visited[n] = 1;
while (!queue.isEmpty()) {
// 수빈이의 현재 위치
Integer currentPosition = queue.poll();
// 수빈이가 움직일 수 있는 방법
int[] move = {currentPosition - 1, currentPosition + 1, currentPosition * 2};
for (int i = 0; i < 3; i++) {
// 수빈이가 움직였는데 동생을 만날 수 있으면
if(move[i] == k) {
result = visited[currentPosition];
return;
}
// 범위 확인
if(move[i] < 0 || move[i] > 100_000) {
continue;
}
// 방문 이력이 없으면
if(visited[move[i]] == 0) {
queue.add(move[i]);
// 깊이를 1 증가
visited[move[i]] = visited[currentPosition] + 1;
}
}
}
}
}백준 12851
visitedTime[move[i]] == visitedTime[currentPosition] + 1부분이 이해가 안돼서 힘들었습니다…
여기서 핵심은 수빈이가 방문한 곳을 다시 방문해도 됩니다.^^
최소 시간만 구하는 문제가 아니라
최소 시간안에서만 동생 위치에 도달하면 되기 때문입니다.
즉, 수빈이가 움직일 수 있는 방법으로 최소시간 안에만 동생이 있는 곳에 도달하면 됩니다.
- 최소시간을 찾습니다.(이 시간이 동생을 찾을 수 있는 제일 빠른 시간입니다.)
- 최소시간을 준수하면서 수빈이는 다른 길로 갈 수도 있습니다.
- 수빈이가 도달한 위치의 시간이 최소시간 보다 크다면 더 이상 탐색을 하지 않아도 됩니다.
풀이
public class Quiz12851 {
static int minTime = Integer.MAX_VALUE;
static int ways = 0;
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 k = Integer.parseInt(st.nextToken());
// 수빈이가 동생보다 앞에 있으면 뒤로가기만 가능..
if(n >= k) {
System.out.print(n-k+"\n1");
br.close();
return;
}
// 방문(시간: 깊이) 기록 배열
// n의 범위가 0 ~ 100_000
int[] visited = new int[100_001];
// bfs 탐색
bfs(visited, n, k);
StringBuilder sb = new StringBuilder();
sb.append(minTime).append("\n").append(ways);
System.out.print(sb);
br.close();
}
private static void bfs(int[] visited, int n, int k) {
Queue<Integer> queue = new ArrayDeque<>();
queue.add(n); // 수빈이의 위치
visited[n] = 1; // 방문 이력(시간, 깊이)
while (!queue.isEmpty()) {
// 수빈이의 현재 위치
Integer currentPosition = queue.poll();
// 수빈이의 현재 위치에 도달한 시간이 최소시간보다 크다면 종료
if(visited[currentPosition] > minTime) {
return;
}
int[] move = {currentPosition - 1, currentPosition + 1, currentPosition * 2};
for(int i = 0; i < 3; i++) {
// 수빈이가 움직여서 동생을 찾았다면
if(move[i] == k) {
minTime = visited[currentPosition];
ways++;
}
// 범위 확인
if(move[i] < 0 || move[i] > 100_000) {
continue;
}
// 수빈이가 움직인 위치에 첫 방문 이거나
// 수빈이가 움직인 위치에 현재 위치에서 1초 안에 도달할 수 있으면
// 수빈이가 다른 움직임으로 동일한 시간에 동생을 찾을 수 있음을 의미
if(visited[move[i]] == 0 || visited[move[i]] == visited[currentPosition] + 1) {
queue.add(move[i]);
visited[move[i]] = visited[currentPosition] + 1;
}
}
}
}
}백준 1012
1012번: 유기농 배추
DFS, BFS 둘다 문제를 해결할 수 있습니다.
[알고리즘] 깊이 우선 탐색(DFS: Depth First Search, 백준 11724, 2606, 11724, 2667)
[알고리즘] 깊이 우선 탐색(DFS: Depth First Search, 백준 11724, 2606, 11724, 2667) 알고리즘 공부를 계속 미루는 제 자신을 보고 이대로는 안되겠다 싶어 😇 본격적으로 코딩테스트를 준비(+알고리즘 공부)
howisitgo1ng.tistory.com
풀이
public class Quiz1012 {
static int n = 0;
static int m = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
// 테스트 갯수
int t = Integer.parseInt(br.readLine());
for(int i = 0; i < t; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
// 배추밭 가로
m = Integer.parseInt(st.nextToken());
// 배추밭 세로
n = Integer.parseInt(st.nextToken());
// 배추 위치 갯수
int k = Integer.parseInt(st.nextToken());
// 배추 밭
int[][] filed = new int[m][n];
for(int j = 0; j < k; j++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
// 배추 심기
filed[x][y] = 1;
}
// 배추밭 방문 이력
boolean[][] visited = new boolean[m][n];
int count = 0; // 지렁이 갯수
for(int x = 0; x < m; x++) {
for(int y = 0; y < n; y++) {
if(!visited[x][y] && filed[x][y] == 1) {
bfs(filed, visited, x, y);
count++;
}
}
}
sb.append(count).append("\n");
}
System.out.println(sb);
br.close();
}
private static void bfs(int[][] filed, boolean[][] visited, int x, int y) {
Queue<Node> queue = new ArrayDeque<>();
queue.add(new Node(x, y));
visited[x][y] = true;
while (!queue.isEmpty()) {
Node node = queue.poll();
int[] upAndDown = {1, -1, 0, 0};
int[] leftAndRight = {0, 0, 1, -1};
for(int i = 0; i < 4; i++) {
// 탐색해야하는 배추밭 위치
int newX = node.getX() + upAndDown[i];
int newY = node.getY() + leftAndRight[i];
// 범위를 벗어난 경우
if(newX < 0 || newY < 0 || newX >= m || newY >= n) {
continue;
}
// 탐색해야하는 곳에 방문 이력이 없고, 배추밭에 배추가 있으면 bfs 실행
if(!visited[newX][newY] && filed[newX][newY] == 1) {
visited[newX][newY] = true;
queue.add(new Node(newX, newY));
}
}
}
}
static class Node {
private int x;
private int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
}
}
728x90
반응형
'0 + 알고리즘(Algorithm)' 카테고리의 다른 글
| [알고리즘] 그리디 알고리즘(백준 11047, 1541, 11399, 1931, 1026 -Java) (0) | 2023.03.24 |
|---|---|
| [알고리즘] 이진 탐색(백준 1920, 10815, 10816, 1654, 2805, 2110 -Java) (0) | 2023.03.24 |
| [알고리즘] 깊이 우선 탐색(DFS: Depth First Search, 백준 11724, 2606, 11724, 2667 -Java) (0) | 2023.03.16 |
| [알고리즘] 삽입 정렬, 퀵 정렬(백준 2750, 1427 -Java) (0) | 2023.03.15 |
| [알고리즘] 버블 정렬, 선택 정렬(백준 2750, 1427 -Java) (0) | 2023.03.13 |