본문 바로가기

BFS22

[백준] 18126번: 너구리 구구 - DFS (Java) 1 . 문제 설명너구리 구구는 N개의 방을 가지고 있다. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이다. 입구는 1개이고, 입구와 모든 방들은 총 N-1 개의 길로 서로 오고 갈 수 있다. 입구에서 최대한 먼 방에 아이스크림을 숨기려고 한다.집 입구에서 아이스크림을 숨기려고 하는 방까지 이동하는 거리를 구한다.방 개수: 1 ≤ N ≤ 5,000모든 길의 정보 A, B, C: 1 ≤ A, B ≤ N, 1 ≤ C ≤ 1,000,000,000A번 방과 B번 방 사이를 양방향으로 연결하는 길의 길이가 C시간 제한: 1초메모리 제한: 1024MB 2. 접근 방식List[] room: N+1 크기의 ArrayList를 사용한다. (인접리스트로 방의 트리 정보 저장)N-1 개의 간선 정보를 .. 2025. 8. 8.
[백준] 17836번: 공주님을 구해라! (Java) 1. 문제설명용사는 (N, M) 크기의 성 입구 (1, 1)로 들어왔다. 성의 여러 군데는 마법 벽이 세워져있고, 용사는 마법 벽을 통과할 수 없다. 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야 한다.저주에 걸린 공주는 T시간 이내에 용사를 만나지 못하면 돌로 변하게 된다. 용사는 한 칸을 이동하는 데 한 시간이 걸리고, 상하좌우로 이동할 수 있다.성에는 전설의 명검 "그람"이 숨겨져 있고, 그람을 구하면 마법의 벽이 있는 칸일지라도, 벽을 부수고 그 공간으로 갈 수 있다. "그람"은 성의 어딘가에 반드시 한 개 존재하고, 용사는 그람이 있는 곳에 도착하면 바로 사용할 수 있다.용사가 공주님을 안전하게 구출할 수 있는지, 얼마나 빨리 구할 수 있는지 구하는 문제이다.시간 제한: 1초메모리 .. 2024. 9. 30.
[백준] 16236번: 아기 상어 (Java) 1. 문제설명N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 한 칸에는 물고기가 최대 1마리 존재한다.가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있으며, 자신의 크기보다 작은 물고기만 먹을 수 있다. 크기가 같은 물고기는 먹을 수 없지만, 지나갈 수 있다.아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 .. 2024. 9. 18.
[백준] 1941번: 소문난 칠공주 (Java) 1. 문제설명총 25명의 여학생들이 5x5의 정사각형 격자 형태로 자리가 배치되어 있다. S(이다솜파)와 Y(임도연파)를 값으로 갖는 5*5 행렬이 주어졌을 때 아래 규칙을 만족하는 모든 경우의 수를 구한다.7명의 학생들로 구성되어야 하고, 7명의 자리는 서로 가로나 세로로 인접해야 한다.7명의 학생 중 S 학생이 적어도 4명 이상은 반드시 포함되어야 한다.시간 제한: 2초메모리 제한: 256MB 2. 접근 방식25자리 중 7자리를 선택하는데, ‘S’ 학생이 4명 이상 포함되도록 한다. (조합, 백트래킹)BFS를 사용해 해당 7개의 자리가 모두 상하좌우로 연결되어 있는지 확인한다.선택된 7명의 자리가 서로 인접한디 BFS로 확인한다. 인접할 경우 count 증가시킨다. 3. 틀린 이유2차원 배열로 백트래.. 2024. 9. 13.
[백준] 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.
[백준] 16954번: 움직이는 미로 탐색 (Java) 1. 문제설명크기가 8x8인 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 체스판 가장 왼쪽 아래 칸에서 가장 오른쪽 윗 칸으로 이동하는 게임을 진행한다. 이 게임에서 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 아래에 행이 없다면 벽이 사라진다. 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 1초 동안 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다.캐릭터가 목표 지점까지 이동할 수 있는지 없는지 구하는 문제이다.시간 제한: 2초메모리 제한: 512MB 2. 접근 방식캐릭터를 (7, 0) 위치에서 출발시킨다. BFS 수행.캐릭터가 이동할 수 있는 위치(상하좌우, 대각.. 2024. 8. 24.
[백준] 1600번: 말이 되고픈 원숭이 (Java) 1. 문제설명 그림은 말의 이동방법을 나타낸다. x 표시한 곳으로 말이 갈 수 있다. 말은 장애물을 뛰어넘을 수 있다. 원숭이는 인접한(상하좌우) 칸으로 이동할 수 있고, 말의 이동방법으로 K번만 움직일 수 있다. 모든 이동은 한 번의 동작으로 친다.원숭이가 격자판의 맨 왼쪽 위에서 맨 오른쪽 아래까지 이동할 때, 동작수의 최솟값을 구하는 문제이다.  시간 제한: 2초메모리 제한: 256MB 2. 접근 방식⇒ 이동하는 동작 수의 최솟값 구하기 → BFS원숭이의 이동 경우를 저장하는 dx1, dy1 배열과 말의 이동 경우를 저장하는dx2, dy2 배열을 사용한다.격자판 (0, 0) 위치에서 BFS 탐색을 시작한다.원숭이의 이동 방법(상하좌우)을 사용하여 인접한 4방향으로 이동을 시도한다.말의 이동 방법을 .. 2024. 8. 24.
반응형