BFS58 [프로그래머스] 118669번 - 등산코스 정하기 [Java] https://school.programmers.co.kr/learn/courses/30/lessons/118669 문제 설명 XX산은 n개의 지점으로 이루어져 있습니다. 각 지점은 1부터 n까지 번호가 붙어있으며, 출입구, 쉼터, 혹은 산봉우리입니다. 각 지점은 양방향 통행이 가능한 등산로로 연결되어 있으며, 서로 다른 지점을 이동할 때 이 등산로를 이용해야 합니다. 이때, 등산로별로 이동하는데 일정 시간이 소요됩니다. 등산코스는 방문할 지점 번호들을 순서대로 나열하여 표현할 수 있습니다.예를 들어 1-2-3-2-1 으로 표현하는 등산코스는 1번지점에서 출발하여 2번, 3번, 2번, 1번 지점을 순서대로 방문한다는 뜻입니다.등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수.. 2025. 3. 6. [백준] 20058번 - 마법사 상어와 파이어스톰 [Java] https://www.acmicpc.net/problem/20058 1. 아이디어 2차원 배열의 회전, 얼음의 양 줄이기, 가장 큰 얼음 덩어리의 크기를 각각 구현해서 합치면 되는 문제로 2차원 배열의 회전읜 격자의 크기와 동일한 크기의 배열과 인덱스의 활용으로, 얼음 양 줄이기는 Queue를 활용해서, 가장 큰 얼음 덩어리의 크기는 BFS, DFS 알고리즘으로 구할 수 있다.2. 문제풀이 얼음판의 크기는 2^N으로 주어지는데 편의를 위해 N을 2^N으로 바꿔서 이용했다. 이를 위해 비트 연산자를 활용했다. 격자의 크기 역시 비트 연산으로 L을 2^L로 바뀌줬고 이후 회전 메서드에서 이용했다. 회전은 두 2차원 배열의 크기가 다른 점만 주의해서 구현하면 된다. 얼음의 양 줄이기는 사방탐색으로 줄여야 하.. 2025. 2. 23. [백준] 2573번 - 빙산 [Java] https://www.acmicpc.net/problem/2573 1. 아이디어 빙산을 녹이는 로직과 빙산의 개수를 구하는 로직을 구분해서 해결했다. 빙산의 개수는 BFS, DFS 알고리즘으로 간단하게 구할 수 있다.2. 문제풀이 빙산을 녹일 때 방금 녹여서 바닷물이 된 부분이 다시 옆 빙산을 녹이는 상황이 발생하게 돼서 각 빙산 주변의 바닷물을 따로 센 후 한번에 빼주는 것만 주의해서 구현하면 된다.3. 코드 import java.io.*;import java.util.*;public class Main_BFS { private static final int[] dr = {-1, 0, 1, 0}; private static final int[] dc = {0, 1, 0, -1}; pu.. 2025. 2. 11. [백준] 17472번 - 다리 만들기 2 [Java] https://www.acmicpc.net/problem/17472 1. 아이디어 BFS, DFS 알고리즘으로 각 섬에 대해 번호를 매긴 후 설치할 수 있는 모든 다리를 찾아서 섬은 노드, 다리를 간선으로 하는 최소 스패닝 트리를 구하는 방식으로 해결했다.2. 문제풀이 각 섬에 번호를 붙여서 섬들을 구분하려고 했고 지도를 순회하며 섬을 발견하면 BFS, DFS 알고리즘으로 해당 섬 전체에 번호를 부여했다. 이후 지도를 순회하며 현재 위치가 섬이면서 오른쪽이 바다인 경우, 현재 위치가 섬이면서 아래쪽이 바다인 경우, 다시 섬을 발견할 때까지 해당 방향으로 계속 가며 섬을 발견하면 이 정보로 다리를 생성해서 우선순위 큐에 넣어줬다. 이후 이 우선순위 큐로 크루스칼 알고리즘을 돌려 모든 섬을 연결하는 다리 .. 2025. 2. 11. [백준] 2146번 - 다리 만들기 [Java] https://www.acmicpc.net/problem/2146 1. 아이디어 BFS 알고리즘으로 각 섬에 대해 번호를 매긴 후 다시 각 섬의 경계부터 다른 섬을 찾을 때까지 최단 거리 BFS를 적용하는 것을 각 섬에 대해 반복해서 해결했다.2. 문제풀이 각 섬에 번호를 붙여서 서로 다른 두 섬을 구분하려고 했다. 입력에서 섬은 1로 주어져 있어서 구분을 위해 번호를 2번부터 매겼으며 해당 섬에 번호를 붙이면서 해당 섬의 경계인 바다는 따로 Queue에 담아줬다. 이후 해당 Queue로 다시 최단거리 BFS를 적용해서 해당 섬이 아닌 좌표를 담아주며 다른 섬을 발견하면 최단 거리를 반환하게 했다.3. 코드 import java.io.*;import java.util.*;public class Main.. 2025. 2. 11. [백준] 9205번 - 맥주 마시면서 걸어가기 [Java] https://www.acmicpc.net/problem/9205 1. 아이디어 상근이네 집과 편의점들, 펜타포트 락 페스티벌을 노드로 각 노드간 거리를 간선으로 하는 그래프에서 두 노드가 연결되었는지 판단하는 문제가 된다. 맥주 1병에 50미터씩 총 1000미터를 한번에 이동할 수 있으므로 간선의 길이가 1000이하인 간선만으로 그래프를 구성한 후 BFS, DFS 알고리즘으로 연결 여부를 파악하면 간단하게 해결할 수 있다.2. 문제풀이 거리가 맨해튼 거리이므로 Math.abs 메서드를 활용했고 상근이네 집을 출발점, 펜타포트 락 페스티벌을 도착점으로 탐색해서 도착할 수 있으면 true, 도착할 수 없으면 false를 반환하는 방식으로 구현했다.3. 코드 import java.io.*;import ja.. 2025. 2. 10. [백준] 16236번 - 아기 상어 [Java] https://www.acmicpc.net/problem/16236 1. 아이디어 우선순위 큐와 BFS를 활용한 시뮬레이션으로 해결할 수 있다.2. 문제풀이 아기 상어와 관련된 정보인 위치와 크기는 static 변수로 관리하며 BFS 알고리즘을 적용했다. 아기 상어의 위치를 입력 받으면 해당 정보로 초기화를 하고 공간에서 아기 상어의 표시인 9를 빈칸인 0으로 변경해서 이후 탐색이 용이하게 했다. 시뮬레이션은 무한 루프에서 BFS를 적용해서 엄마 상어에게 도움을 요청하는 표시인 -1을 반환하면 종료하고 아니면 누적 시간을 더하고 먹은 물고기를 세줬다. 먹은 물고기 수가 아기 상어의 크기와 같아지면 아기 상어의 크기를 키우고 먹은 물고기 수를 0으로 초기화했다. BFS는 아기 상어가 물고기를 먹는 조건이.. 2025. 2. 10. [백준] 17142번 - 연구소 3 [Java] https://www.acmicpc.net/problem/17142 1. 아이디어 이전 연구소 문제에서 이제 바이러스가 비활성 상태로 존재하고 활성 시킬 일부 바이러스를 선택했을 때로 바뀐 문제이다. 비활성 상태로 존재하는 바이러스도 맵에 바이러스로 존재하는 것을 고려해서 BFS 종료 조건을 변경하면 간단하게 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 17141번 - 연구소 2 [Java])2. 문제풀이 초기 비활성 바이러스의 수를 virusCnt로 센 후 BFS 알고리즘을 적용했다. 종료 조건은 동일하지만 BFS에서 최단거리가 갱신될 때마다 수행하는 방식으로 구현했고 활성 바이러스가 퍼질 때 비활성 바이러스가 존재하는 칸으로 퍼지면 Queue에는 넣지만 바이러스의 수를 세지는 않는 방식으.. 2025. 2. 4. [백준] 17141번 - 연구소 2 [Java] https://www.acmicpc.net/problem/17141 1. 아이디어 이전 연구소 문제에서 이제 바이러스를 놓을 수 있는 칸 중 바이러스를 M개 놓고 모든 위치에 바이러스를 퍼트릴 수 있는 최소 시간을 구하는 문제로 조합을 통해 바이러스를 퍼트릴 위치를 정한 후 최단거리 BFS를 통해 바이러스가 모두 퍼졌으면 최단거리를 반환하는 방식으로 해결했다.([코딩테스트 준비/백준] - [백준] 14502번 - 연구소 [Java])2. 문제풀이 빈칸 없이 바이러스가 퍼졌는지 알기 위해 벽의 개수를 wallCnt로 저장하고 바이러스를 놓을 수 있는 칸을 리스트로 저장했다. 이후 리스트에 대한 조합을 구해서 최단거리 BFS를 수행 후 이를 현재까지 구한 최단 시간과 비교 갱신하는 방식으로 구현했다. 최단.. 2025. 2. 4. [백준] 14502번 - 연구소 [Java] https://www.acmicpc.net/problem/14502 1. 아이디어 주어진 빈 칸 중 세 개를 뽑아 벽으로 만들고 시뮬레이션을 돌린 후 다시 빈 칸으로 만드는 과정을 반복하면 해결할 수 있다. 벽을 정확히 3개를 세우면 돼서 3중 for문을 활용했고 시뮬레이션은 BFS 알고리즘을 활용했다.2. 문제풀이 입력에서 빈칸과 바이러스의 위치는 각각 리스트에 저장 후 3중 for문으로 빈칸 리스트에서 3개를 뽑아 벽으로 바꾼 후 바이러스의 위치를 통해 BFS 알고리즘을 적용했다. 이후 벽을 빈 칸으로 바꿔주면 된다.3. 코드 import java.io.*;import java.util.*;public class Main { private static class Node { int.. 2025. 2. 4. [백준] 14248번 - 점프 점프 [Java] https://www.acmicpc.net/problem/14248 1. 아이디어 BFS와 DFS 알고리즘을 활용하면 간단하게 해결할 수 있다.2. 문제풀이 시작 위치에서 왼쪽 또는 오른쪽으로 점프를 하고 다시 이동한 위치에서 왼쪽 또는 오른쪽으로 이동하는 것을 반복하는 문제로 점프할 위치가 방문 가능한 위치인지만 체크하는 BFS, DFS로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main_BFS { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Sys.. 2025. 2. 4. [백준] 11967번 - 불켜기 [Java] https://www.acmicpc.net/problem/11967 1. 아이디어 스위치가 있는 방에 방문해서 불을 켰을 때 불이 켜지게 된 방이 과거에 방문할 수 있었던 방이면 방문을 해야하는 문제이다. 이를 위해 현재 불이 꺼져있지만 방문할 수 있었던 방에 대한 방문체크를 별도로 진행해서 불을 켰을 때 해당 방이 이전에 방문할 수 있었던 방이면 방문할 수 있도록 했다.2. 문제풀이 특정 방에 여러 개의 스위치가 존재할 수 있는 상황으로 리스트를 받는 2차원 배열로 입력을 처리했다. BFS에서 변수로 불이 켜진 상태를 표시하는 원본 맵인 boolean 타입 2차원 배열과 실제 방문, 임시 방문을 담당하는 방문 체크 배열을 사용했다. 로직은 현재 방에 스위치가 있으면 불을 켜고 불을 킨 방이 임시 방문.. 2025. 2. 3. 이전 1 2 3 4 5 다음
