본문 바로가기
반응형

알고리즘 PS/BFS10

[백준] 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.
[백준] 2206번 - 벽 부수고 이동하기 (Java)(△) https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 1. 최단거리 구하기 문제이므로 BFS 탐색을 사용하면 된다. 2. 벽을 한개까지 부술 수 있다. 탐색 시에 벽을 만나도 한번 더 나갈 수 있다는 뜻. 2-1. 최대 한개까지 1 -> 0으로 바꿀 수 있다. 2-2. 벽 공사 여부를 변수로 넣고 dist 배열을 dist[N][M][2]개로 만들어서 관리 2-3. 벽을 한번도 안 뚫은 경우는 dist[][][0]으로 거리 저.. 2022. 9. 20.
[백준] 14502번 - 연구소 (Java)(△) https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 1. 바이러스가 퍼지는 걸 막으려면 벽을 세워야 하는데 벽의 개수는 3개이다. 2. 바이러스가 상하좌우로 번질 수 있다고 하니 BFS에서 큐에 넣은 것은 바이러스의 위치이다. 2-1. BFS 호출 전에 for문을 돌려서 바이러스(2)를 다 큐에 넣자. 3. 이 문제는 탐색을 2번을 해야 한다. (벽 3개를 세우는 경우의 수, 바이러스 확산의 경우의 수) 3-1. 벽 3개를 완전탐색(DFS)해서 하나씩 세우다가.. 2022. 9. 12.
[백준] 2178번 - 미로 탐색 (Java)(◎) https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 1. 미로에서 처음에서 끝까지 가는 최단거리를 구하는 문제이다. 2. 미로 입력에 공백이 없으므로 한줄 씩 string 문자열로 받고, 한글자씩 배열로 저장한다. 3. 방문체크를 위한 visited 배열을 준비하고, 첫 시작인 (1, 1)을 true로 설정한다. 4. BFS 알고리즘으로 상/하/좌/우로 탐색해서 1이면 이동하고 0이면 스킵한다. 5. 최단거리를 구하기 5-1. map 배열의 다음 탐색지에 누적거리+1을 덮어쓰면서.. 2022. 9. 6.
[백준] 2606번 - 바이러스 (Java)(◎) https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 1. 컴퓨터 번호가 정점, 네트워크가 간선이다. 2. 바이러스가 감염되는 컴퓨터의 수는 간선을 통해 방문할 수 있는 정점의 수와 일치한다. 3. 1번 정점부터 dfs로 탐색을 해서 마지막에 카운팅한 수를 출력하면 된다. 4. 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력이니까 1번 컴퓨터는 카운팅하면 안된다. 1. 인접배렬로 입력값을 저장하고, 배열번호는 정점의 번호와 동일하게 1~.. 2022. 8. 31.
반응형

티스토리툴바