BFS9 [알고리즘] 아기상어 (백준 16236번) 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 예전에 푼 적이 있는 문제임에도 생각보다 시간이 더 오래 걸렸다. 그것도 예전에 풀었던 솔루션보다 시간이 더 길게 나오더라..;; BFS + 시뮬레이션 방식의 문제이다. N의 범위가 작아서 시간초과 걱정없이 풀 수 있는 문제이다. Solution fish_count : map에 있는 총 물고기의 수. queue에 맨 처음 상어 위치를 넣는다. fish_count가 1마리 이상 있으면 계속 반복문 진행 bfs 탐색 시작 현재 위치에서 최단 거리에 있는 먹.. 2020. 9. 17. [알고리즘] 등굣길 (프로그래머스 Level3) 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 문제 그림만 봐도 느껴지겠지만 탐색 문제이다. 다만 문제에서 최단 경로라고 언급을 했으니 BFS를 이용하기로 했다. 하지만 Level3 문제답게 단순한 BFS 문제는 아니다. 단순히 '최단 경로' 만 구하라고 한 것이 아니라 '최단 경로의 개수'를 구하라고 했다. 즉 특정 노드를 기준으로 그곳에 도착한 경로들의 개수들을 세어야 하고 이것은 동적 프로그래밍을 이용해서 메모이제이션해야한다. 즉 BFS + DP 문제이다. (추후에 알게된 사실인데 BFS도 .. 2020. 9. 7. [알고리즘] 벽 부수고 이동하기 (백준 2206번) 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net 지도의 끝까지 이동할 때의 최단 경로를 구하는 BFS 문제이다. 다만 벽을 1개까지 부수고 이동할 수 있다는 조건이 있다. 만약에 브루트 포스로 구한다고 가정해보자. 모든 경우의 수를 따지려면 맵의 벽의 개수 만큼 BFS를 돌려야 하는데 한 번 BFS를 돌릴 때 최악의 연산 횟수가 3백만번 정도된다. (O(V+E) = 1000 * 1000 + 1000 * 999 + 1000 * 999) 거기에 벽의 개수 최악의 경우 NM개를 곱하게 .. 2020. 9. 3. [알고리즘] 중량제한 (백준 1939번) 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리 www.acmicpc.net 전형적인 'BFS + BinarySearch' 유형의 문제이다. BinarySearch로 최대값 혹은 최소값을 찾되 BFS로 현재 값이 타당한지를 판단하는 문제 유형이다. Solution 이 문제는 트럭에 실릴 수 있는 최대 중량을 구하라는 문제이다. 만약 트럭의 특정 중량을 기준으로 도착지까지 갈 수 없다면, 그보다 더 높은 중량으로는 당연히 도착지까지 갈 수가 없기에 search하는 값들이 정렬이 되어 있기에 .. 2020. 9. 1. 이전 1 2 3 다음
