본문 바로가기

분류 전체보기154

[백준] 7569번: 토마토 (Java) 1. 문제설명토마토는 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 보관한다. 익은 토마토와 아직 익지 않은 토마토가 있고, 보관 후 하루가 지나면 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들이 익게 된다. 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향이다.창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소일수를 구하는 문제이다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.시간 제한: 1초메모리 제한: 256MB 2. 접근 방식⇒ 최소 일자 구하기 -> BFS 사용상자에 있는 토마토의 정보를 저장하는 `int[][][] box` 배열 사용한다.일자를 저장.. 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.
[백준] 14675번: 단절점과 단절선 (Java) 1. 문제설명단절점: 해당 정점을 제거하였을 때, 그 정점이 포함된 그래프가 2개 이상으로 나뉘는 경우단절선: 해당 간선을 제거하였을 때, 그 간선이 포함된 그래프가 2개 이상으로 나뉘는 경우주어진 간선 정보를 통해 질의 “t k”의 답을 ‘yes’ 또는 ‘no’로 출력하는 문제이다.t가 1일 때는 k번 정점이 단절점인지에 대한 질의, t가 2일 때는 입력에서 주어지는 k번째 간선이 단절선인지에 대한 질의이다.시간 제한: 1초메모리 제한: 512MB 2. 접근 방식트리의 간선 정보를 인접 리스트로 저장한다.질의 t가 1인 경우 (단절점인지)해당 정점의 간선 개수가 2개 이상인 경우 → “yes” 출력아닌 경우 → “no” 출력질의 t가 2인 경우 (단절선인지)무조건 2개의 그래프로 나눠짐 → “yes” .. 2024. 8. 14.
[백준] 11725번: 트리의 부모 찾기 (Java) 1. 문제설명트리의 루트를 1이라고 정했을 때, 주어진 트리에서 각 노드의 부모를 구하는 문제이다.시간 제한: 1초메모리 제한: 256MB 2. 접근 방식=> DFS와 BFS 모두 풀이 가능하다.인접 리스트를 사용해 트리의 노드 정보를 저장한다.각 노드를 탐색하며 DFS를 사용해 각 노드의 부모를 저장한다.방문 체크하는 `visited` 배열 사용부모 정보 저장하는 `parent` 배열 사용 3. 최종 코드import java.io.*;import java.util.*;public class Main { static int n; // 노드의 개수 static ArrayList[] list; // 노드 저장 static boolean[] visited; // 방문 여부 체크 stati.. 2024. 8. 14.
[백준] 7578번: 토마토 (Java) 1. 문제설명토마토는 격자 모양 상자의 칸에 하나씩 보관된다. 익은 토마토의 인접한(상하좌우) 곳에 있는 익지 않은 토마토들만 익은 토마토의 영향을 받아 익게 된다. 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 구하는 문제이다.만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력, 토마토가 모두 익지 못하는 상황이면 -1을 출력한다.시간 제한: 1초메모리 제한: 256MB 2. 접근 방식⇒ 모든 토마토가 익는 최소 시간을 구하는 문제 → BFS토마토 정보를 담은 `int[][] box`를 사용한다.상하좌우로 이동할 수 있는 배열(dx, dy)을 사용한다.익은 토마토를 큐에 추가한다. (위치 정보)큐가 빌 때까지큐에서 값을 꺼내, 이 위치의 상하좌우를 탐색한다. (`.. 2024. 8. 13.
반응형