본문 바로가기

DFS14

[백준] 1743번: 음식물 피하기 (Java) 1. 문제설명음식물이 통로 중간 중간에 떨어져 있고, 음식물은 근처(상하좌우)에 있는 것끼리 뭉치게 되어 큰 음식물 쓰레기가 된다. 떨어진 음식물 중에 제일 큰 음식물의 크기를 구하는 문제이다.시간 제한: 2초메모리 제한: 128MB 2. 접근 방식음식물 쓰레기가 있는 위치를 load배열에 저장한다. 음식물이 있는 곳을 1로 저장한다.(0, 0) 위치부터 통로를 BFS 탐색한다.큐를 사용해 인접한 상하좌우를 탐색하여 연결된 음식물의 크기를 계산한다.BFS를 통해 구한 음식물의 크기(trashSize)를 maxTrashSize와 비교하여 최댓값을 갱신한다.  3. 최종 코드import java.io.*;import java.util.*;public class Main { static int n, m;.. 2024. 8. 25.
[백준] 14620번: 꽃길 (Java) 1. 문제설명씨앗은 꽃을 심고나면 1년 후에 꽃이 핀다. 꽃의 씨앗은 세 개밖에 없으므로 세 개의 꽃이 하나도 죽지 않고 1년 후에 꽃잎이 만개하게 한다. 꽃밭은 N*N의 격자 모양이고 씨앗은 (1,1)~(N,N)의 지점 중 한 곳에 심을 수 있으며 꽃이 피면 격자 모양의 위치를 차지한다. 꽃은 다른 꽃잎 또는 꽃술과 닿게 될 경우 두 꽃 모두 죽고, 화단 밖으로 나갈 경우도 꽃이 죽게 된다.화단의 지점 당 가격이 주어지고, 세 개의 씨앗이 모두 꽃이 피게 하는 최소 비용을 구하는 문제이다.시간 제한: 2초메모리 제한: 256MB 2. 접근 방식DFS를 사용하여 3개의 꽃을 심을 수 있는 위치를 탐색한다.꽃을 심을 위치를 선택할 때, 꽃과 꽃잎이 차지하는 위치를 방문하지 않았는지 확인한다.만약 3개의 꽃.. 2024. 8. 24.
[백준] 2146번: 다리 만들기 (Java) 1. 문제설명  NxN 크기의 이차원 평면상에 나라가 존재한다. 이 나라는 여러 섬으로 이루어져 있다. 육지가 없는 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다.두 대륙을 연결하는 가장 짧은 다리 하나를 구하는 문제이다. (길이 구하기)   시간 제한: 2초메모리 제한: 192MB 2. 접근 방식섬 구분 → BFS를 사용하여 각 섬에 번호를 부여한다.최소 다리 길이 계산BFS를 사용하여 각 섬에서 다른 섬까지의 최단 거리를 계산한다.바다인 곳으로 확장하면서 다른 섬에 도달할 때까지의 거리를 구하고, 이 중 짧은 거리를 찾는다. 3. 최종 코드import java.io.*;import java.util.*;public class Main { static int n; // 지도의 크기 .. 2024. 8. 23.
[백준] 13023번: ABCDE (Java) 1. 문제설명N명의 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.친구 관계가 주어질 때, 조건에 맞는 친구 관계가 존재하는지 구하는 문제이다.시간 제한: 2초메모리 제한: 512MB 2. 접근 방식인접 리스트 형태로 친구 관계를 저장한다.DFS를 사용해 각 노드로부터 시작해서 5명의 친구 관계가 나올 수 있는지 확인한다.DFS에서 방문한 노드를 확인하기 위해 `visited` 배열을 사용한다. 이때 DFS를 호출하고 난 후, 방문 처리한 것을 되돌린다. (백트래킹) 3. 틀린 이유인접 행렬을 사용해서 “시간 초과”가 나왔다.⇒ 인접 리스트를 사용하는 방식을 사용했다. 4. 최종 코드import java.io.*;import java.util.*;public class Mai.. 2024. 8. 20.
[백준] 12851번: 숨바꼭질 2 (Java) 1. 문제설명수빈이가 점 N(0 ≤ N ≤ 100,000)에 있고, 동생이 점 K(0 ≤ K ≤ 100,000)에 있다.수빈이가 X일 때 1초 후에 X-1 또는 X+1, 2*X의 위치로 이동할 수 있다.수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후이고, 가장 빠른 시간으로 찾는 방법의 수를 구하는 문제이다.시간 제한: 2초메모리 제한: 512MB 2. 접근 방식⇒ 최단 경로 구하기 → BFS각 위치에 도달하는 시간을 `time` 배열에 저장 (최소 시간을 계산)BFS를 사용해 각 위치에서 이동 가능한 위치를 큐에 넣고 탐색한다.방문한 위치에 도달한 시간을 저장한다. (`time` 배열에)동생의 위치에 도달하게 되면이동 시간이 최소 시간인지 확인하고, 최소 시간을 갱신한다.이동 시간이 현재까지.. 2024. 8. 17.
[백준] 14502번: 연구소 (Java) 1. 문제설명바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소 크기는 N x M인 직사각형으로 나타낼 수 있고, 연구소는 빈 칸과 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이다. (꼭 3개)주어진 연구소 정보에서 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다.벽 3개를 세운 뒤, 바이러스가 퍼질 수 없는 안전 영역 크기의 최대값을 구하는 문제이다.시간 제한: 2초메모리 제한: 512MB 2. 접근 방식연구소에 3개의 벽을 세우는 모든 경우를 DFS를 통해 구한다. (백트래킹 사용)3개의 벽을 세운 경우 바이러스를 퍼트리는 과정에 BFS를 사용하여, 안전 구역을 구한다.. 2024. 8. 16.
[백준] 2667번: 단지번호붙이기 (Java) 1. 문제설명정사각형 모양의 지도가 있고 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 이 지도를 보고 상하좌우로 연결된 단지에 번호를 붙이려고 한다. 이 지도에서 나올 수 있는 총 단지 수를 구하고, 각 단지내 집의 수를 오름차순으로 구하는 문제이다.시간 제한: 1초메모리 제한: 128MB 2. 접근 방식⇒ 지도의 인접한 단지들을 모두 구해야 하므로 DFS/BFS를 사용한다.지도 정보를 인접 행렬 형태로 저장한다.(1, 1)부터 (N, N)까지 단지의 수와 각 단지 내 집의 수를 구한다.상하좌우로 이동 가능하고 집이 있는 곳을 DFS 재귀 호출한다.단지 내 집의 수를 List로 저장한다.List의 크기가 “단지 수”List를 오름차순 정렬하여 “단지 내 집의 수”를 출력한다. 3. 최종 코드D.. 2024. 8. 15.
반응형