BFS

[백준] 2573 빙산 (JAVA)

✉️문제 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 📝 접근 이 문제를 위해서 필요한 기능은 크게 2가지이며, BFS와 DFS를 모두 이용한다. 1. 빙산의 개수를 확인하는 코드 (DFS) 2. 빙하를 녹이는 메소드 (BFS) TIP ! 배열을 선언할 때 x,y 변수명을 이용하면 더 헷갈리는 것 같다. 이 때는 row와 col 변수명을 이용하는 것이 더 편하다. 🗝 문제풀이 1. 빙산의 개수를 확인하는 코드 (두개의 메소드로 분리하였..

[백준] 5014 스타트링크 (JAVA)

✉️문제 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 📝 접근 먼저 문제를 예제를 통해 이해해보자. [ 10, 1, 10, 2, 1 ] 의 입력이 들어왔을 때 이는 다음과 같다. -> 건물은 10층으로 구성되어 있고 강호는 현재 1층에 있다. 스타링크까지 가야하는데 현재 스타링크의 위치는 10층에 있으며, 올라갈 때는 2층씩 올라갈 수 있고 내려갈 때는 1층씩 내려갈 수 있다. 이 때의 최단 거리를 구하는 문제이다. 필자는 최단 거리를 구할 때는 보통 ..

[백준] 1697 숨바꼭질 (JAVA)

✉️문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 📝 접근 최단거리를 구하는 문제이다. DFS로 풀 수 있을 것 같지만, DFS로 구현하면 커팅 기법을 사용해도 지수 시간 복잡도를 가지기 때문에 시간 내에 통과하기 어렵다. 따라서 BFS를 이용해야 한다. 🗝 문제풀이 package baekjoon; import java.util.LinkedList; import java.util.Queue; import jav..

[백준] 7569 토마토 (JAVA)

✉️문제 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 📝 접근 7576번과 똑같은 BFS 문제이다. 여기서 배열이 2차원 -> 3차원으로 변경된 문제라고 생각하면 된다. https://brightmango.tistory.com/323 [백준] 7576 토마토 (JAVA) ✉️문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주..

[백준] 7576 토마토 (JAVA)

✉️문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 📝 접근 Queue를 이용한 BFS를 이용한다. 🗝 문제풀이 1. 입력을 받을 때 input == 1이면 큐에 집어넣는다. // 입력을 받을 때 input == 1이면 큐에 집어넣는다. for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { int input = sc.nextInt(); box[i][j] = input; if..