본문 바로가기

분류 전체보기153

[백준] 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.
[백준] 7562번: 나이트의 이동 (Java) 1. 문제설명  왼쪽 그림은 체스판에서 나이트가 한 번에 이동할 수 있는 칸이다.현재 나이트가 있는 칸, 나이트가 이동하려고 하는 칸이 주어졌을 때, 나이트가 몇 번의 움직임으로 목표 칸에 도달할 수 있는지 구하는 문제이다.   시간 제한: 1초메모리 제한: 256MB 2. 접근 방식나이트가 현재 있는 칸 부터 BFS를 수행한다.나이트가 이동할 수 있는 칸으로 탐색하고, 이동하는 위치에 현재 위치까지의 거리 + 1을 저장한다.목표 지점에 도달하면 해당 칸의 거리를 출력한다.  3. 최종 코드import java.io.*;import java.util.*;public class Main { static int l; // 체스판 한 변의 길이 static int[][] board; // 체스판 .. 2024. 8. 23.
[백준] 2206번: 벽 부수고 이동하기 (Java) 1. 문제설명NxM의 행렬로 표현되는 맵에서 0은 이동할 수 있는 곳, 1은 이동할 수 없는 곳을 나타낸다. (1, 1)에서 (N, M)까지 이동할 때 최단 경로로 이동하려 한다. 만약 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 더 짧은 경로가 된다면, 벽을 한 개까지 부수는 것이 허용된다.주어진 맵에서 최단 경로를 구하는 문제이다.시간 제한: 2초메모리 제한: 192MB 2. 접근 방식⇒ 최단 거리를 찾는 문제이기 때문에 BFS 문제이지만, 벽을 한 번 부수는 것을 허용하는 조건 때문에 한 번의 BFS로 해결할 수 없다.각 위치에서 벽을 부수지 않은 상태와 벽을 부순 상태를 모두 고려해야 한다.`visited[i][j][0]`: (x, y) 위치에 벽을 부수지 않은 상태로 방문했는지`visit.. 2024. 8. 21.
[백준] 16234번: 인구 이동 (Java) 1. 문제설명NxN 크기의 땅이 있고, 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 인구 이동은 하루동안 아래와 같이 진행되고, 더이상 인구 이동이 없을 때까지 지속된다.각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 문제이다.시간 제한: 2초메모리 제한: 512MB 2. 접근 방식while문으로 인구 이동이 일어났는지 확인하고, 더 이상 인구 이동이 발생하지 않을 때까지 반복한다.매 반복 시작 시, 방문 여부 확인하는 배열(`visited`)를 초기화하고, 모든 나라에 대해 방문하지 않은 경우 BFS 탐색한다.인접한 나라와의 인구 차이가 조건에 부합하면큐에 해당 위치를 넣고 방문 처리.. 2024. 8. 21.
[백준] 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.
[백준] 7569번: 토마토 (Java) 1. 문제설명토마토는 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 보관한다. 익은 토마토와 아직 익지 않은 토마토가 있고, 보관 후 하루가 지나면 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들이 익게 된다. 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향이다.창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소일수를 구하는 문제이다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.시간 제한: 1초메모리 제한: 256MB 2. 접근 방식⇒ 최소 일자 구하기 -> BFS 사용상자에 있는 토마토의 정보를 저장하는 `int[][][] box` 배열 사용한다.일자를 저장.. 2024. 8. 20.
반응형