BFS5 [1600] 말이 되고픈 원숭이 - C++ 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 1. 문제 요약 정해진 횟수에 한해서 원숭이가 말처럼 움직이며 장애물을 하나 넘어갈 수 있다, 횟수를 모두 소진하면 원숭이처럼만 움직일 수 있다. 이렇게 움직여서 맨 오른쪽 아래에 도착하는 최소한의 이동 횟수를 구하라 2. 전략 BFS를 사용하며 지금까지 이동한 횟수를 적을 이차원 배열을 사용하면 될 것 같다. 라고 생각하면 큰코다친다. 내가 그랬다. 일반적인 이차원 배열로는 해결이 안 됐는데, 그 이유가 횟수가 다 소진될 때까지 말처럼 행동하다.. 2023. 8. 23. [2146] 다리 만들기 - C++ 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 1. 문제 요약 대륙간의 놓을 수 있는 다리 중 가장 짧은 다리의 길이를 알아내야 함 2. 전략 BFS를 써야 하는 것은 너무도 당연하다. 내가 생각한 방법은 정말 간단하다, 바다옆에 육지가 있는 부분에서 모두 BFS를 돌려 보는 것이다. 그런데 위의 방법에는 한 가지 문제가 있다. 내가 출발한 대륙에서 BFS를 돌려 다른 대륙에 도착한 건지, 아니면 빙 돌아와 내가 서 있었던 대륙에 다시 도착한 건지 알 방법이 없다. 이 문제를 해결하기 위해서 나는 각 대륙마다 고.. 2023. 8. 23. [16236] 아기 상어 - C++ 풀이 이번 글에서는 어떻게 구상하고 설계했는지 자세하게 적어 보려고 한다 1. 나에게 가까운 것을 찾아야 한다. BFS를 사용할 수 있을 듯하다. 가까운 것이 여러 개 있다면 가장 위에 있는 것, 그중에서도 여러 개 있다면 가장 왼쪽의 것을 고르라 하니 BFS를 돌고 for문을 사용해도 될 듯하다. 시간을 표시해줘야 하니 Dist라는 -1로 채워진 $ N \times N $ 배열을 만들어 줘야 한다. 2. 상어를 성장시켜야 한다. baby라는 상어의 현재 크기를 담는 변수 growing이라는초기값은 0이고, 물고기를 먹을 때마다 증가시킨다. 만약 baby 변수와 값이 동일해진다면 baby증가, growing은 0으로 초기화 즉 상어의 무게를 늘려주는 식으로 구상했다. 3. 종료 조건 무한 반복을 돌리며 .. 2023. 6. 27. [1018] 체스판 다시 칠하기 - C++ https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 이게 실버 4라고? ㅎ... 풀이를 시작하기전 말할 것이 있다면 나는 좀 이상하게 푼 것 같다.... 뭐지 일단 시작 하겠다. 풀이 ( 주의! ) 처음에 문제 이해를 잘못한 나머지 항상 B 일 때만 계산했다. 왼쪽 위가 B로 시작할 때, W로 시작할 때 둘 다 계산해줘야 한다. 가장 먼저 우리가 해야 하는 8 x 8로 자를 수 있는 모오오든 경우의 수를 구해야 한다. 8 x 8로자를 수 있.. 2023. 6. 19. 14923 - c++ https://www.acmicpc.net/problem/14923 14923번: 미로 탈출 홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 www.acmicpc.net 요약 1. 현재 나의 위치와 탈출가능한 위치가 있다 2. 벽을 딱 한번 부술 수 있다. 벽을 부수고 최단 경로를 구하는 것 아이디어 예전에 비슷한 문제를 풀었던 적이 있다. 벽을 부순 상태일 때의 배열을 따로 만드는 방법으로 풀었던 기억이 있다. 그것과 비슷하게 dist [n][m][2]라는 배열을 만들고 dist[a][b][0] // 벽을 부수지 않은 상태 dist[a][b][.. 2023. 6. 1. 이전 1 다음
