본문 바로가기
반응형

BFS28

[백준] 7569번 - 토마토 (Java)(○) https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net - 백준 7576 토마토 문제의 확장판이다. z축이 추가가되었다. - z축(위, 그대로, 아래)가 추가가 되었으므로 6방향을 탐색해야 한다. static int dx[] = {-1, 0, 1, 0, 0, 0}; static int dy[] = {0, 1, 0, -1, 0, 0}; static int dz[] = {0, 0, 0, 0, -1, 1}; 상하좌우위아래로 확산하면서.. 2023. 5. 22.
[백준] 16236번 - 아기 상어 (Java)(○) https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 맵의 크기는 N * N 물고기 M마리와 아기상어 1마리 아기상어와 물고기는 자연수로 표시된 크기를 가진다. 처음에 아기상어의 크기는 2이고, 1초에 상하좌우로 한칸씩 움직일 수 있다. * 아기상어 이동조건 1. 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없다. 2. 자기보다 크기가 작은 물고기만 먹을 수 있다. 3. 같은 물고기가 있는 칸은 먹을 수는 없고 지나갈 수만 있다. 4. .. 2023. 3. 19.
[백준] 16954번 - 움직이는 미로 탈출 (Java)(○) https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 1. 체스판의 크기는 8 x 8이다. 모든 판은 빈 칸(.)과 벽(#)으로 되어 있다. 2. 가장 왼쪽 아래 칸에서 가장 오른쪽 윗 칸으로 이동해야 한다. 3. 1초마다 모든 벽이 아래에 있는 행으로 한칸씩 이동한다. 만약 가장 아래 였으면 벽이 사라진다. 4. 캐릭터는 인접한 한 칸 또는 대각선으로 이동하거나, 현재 위치에 서 있을 수 있다. 5. 1초 동안 캐릭터가 먼저 이동하고, .. 2023. 3. 13.
[백준] 7576번 - 토마토 (Java)(○) https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 토마토를 보관하는 창고(N * M)이 있다. 칸 마다 토마토를 보관한다. 토마토는 익은 것과 덜 익은 것들이 섞여 있다. 보관 후 하루가 지나면 잘 익은 토마토의 상/하/좌/우에 있는 토마토들도 익게 된다. 토마토가 혼자서 익는 경우는 없고 반드시 영향을 받아서 익는다. 창고의 토마토들이 모두 익게 되는 최소 일수를 구하라. 상자의 일부 칸에 토마토가 없는 경우도 있다. 상하좌우로.. 2023. 3. 2.
[백준] 1525번 - 퍼즐 (Java)(△) https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 1. 숫자가 이동하는 것이 아니라 0번이 이동하는 것으로 바꿔서 생각하자. 2. 0의 좌표를 이동하면 그 위치의 숫자를 원래 0의 위치로 옮긴다. 3. 메인함수에서 0의 위치를 찾아서 DFS()를 호출한다. 4. DFS 함수 구성 (int count, int x, int y) - count : 0의 이동 횟수 - x, y : 0이 이동한 위치 - 종료조건 : 0이 (2, 2)의 위치로 이동 - 퍼즐의 유효성 검사를 수행하는 함수를 실행 - 재귀호출은 0을 하나 이동 시키고 .. 2022. 12. 20.
[백준] 2665번 - 미로만들기 (Java) https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 검은 방을 변경하는 로직을 어떻게 가져 가야할 지 고민이 되었다. 처음엔 백준 14502 연구소 문제와 비슷한 유형으로 생각하고 아이디어를 생각해보았다. 랜덤하게 검은방 하나씩 변경하고 BFS탐색을 하는 식으로 진행해 봤는데 14502와는 차이점이 그 문제는 문 3개가 되면 탐색을 시작한다는 명확한 재귀탈출 조건이 있었고, 이 문제는 조건 세우기가 애매했다. 검은방의 위치, 갯수... 랜덤하게 진.. 2022. 10. 27.
[백준] 1926번 - 그림 (Java) https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net map : 1과 0으로 구성. 그림 : 상하좌우가 1로 연결된 것 그림의 갯수와 가장 큰 그림의 넓이를 출력한다. 그림이 하나도 없는 경우에는 가장 큰 그림의 넓이는 0을 출력한다. 입력정보 세로축 N : 2022. 10. 10.
[백준] 14496번 - 그대, 그머가 되어 (Java) https://www.acmicpc.net/problem/14496 14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000) 이후 M개의 줄에 걸쳐 치환 가능한 문 www.acmicpc.net 문자열 a를 b로 바꾸는 최소 치환 횟수를 구하는 문제이다. 문자열 관련 문제처럼 보이나 실상은 문자열 a에서 b로 가는 최단경로를 구하는 문제이다. 우선순위 큐와 다익스트라 알고리즘을 사용해서 풀면된다. 인접리스트 방식 둘로 나눠서 풀어보자. 1. class Node를 구성하자. cost로 오름차순으로 PQ를 구성한다. 2. 방문배열(boolean v.. 2022. 10. 8.
[백준] 3055번 - 탈출 (Java) https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 지도는 R행 C열로 이루어짐. 비어있는 곳 '.' 물이 차있는 곳 '*' 돌은 'X' 비버의 굴은 'D' 고슴도치의 위치는 'S' 고슴도치는 매분마다 인접한 상/하/좌/우의 칸 하나로 이동할 수 있다. 물도 매분마다 인접한 비어있는 칸으로 확장한다. (이것도 상/하/좌/우?) 물과 고슴도치는 돌을 통과할 수 없다. 고슴도치는 물로 차있는 지역으로 이동할 수 없다. 물도 비버의 굴로 이동할 수 없다. 고슴도치는.. 2022. 10. 5.
반응형

티스토리툴바