16236번: 아기 상어
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가
www.acmicpc.net
| 문제를 2덩어리로 나눠서 생각하면 편한 문제이다. |
| 현재 위치에서 어디로 가야할 지 찾는 부분(bfs(shark_x, shark_y, v, shark_size) 함수가 담당. 이거는 최악의 경우 n^2 시간이 걸림. 최악의 경우 배열의 모든 원소를 다 따져봐야 하는 경우도 있으니까) |
| 그리고 이차원 배열의 모든 원소의 위치마다 그 경우를 따져야 하니까(main함수의 while문에서 담당). 그것도 최악의 경우 n^2만큼 걸린다. |
| 즉 n^2 * n^2 = O(n^4) 만큼의 시간복잡도가 소요된다! |
<추가적으로 학습한 내용>
- vector의 자료형으로 tuple을 썼을 때, 출력하는 법
e.g.) vector< tuple<int, int, int> > v로 선언하고, v[2]의 1번째 원소 출력 하고 싶으면 // get<1>(v[2]) 라고 하면 된다!
- 이차원 배열을 vector로 선언하는 법
e.g.) vector< vector<int> > v(n,vector<int> (n)) // vector<int> 자료형을 띄고 있는 원소 n개를 넣을 건데, 그 원소들은 각각 int 형의 원소 n개를 가지고 있다는 의미. 다시말해, n x n 2차원 배열(모든 원소는 int형)을 선언하는 의미와 비슷하다.
소스코드 : github.com/shinbian11/ProblemSolving/commit/9b3ddbb980d7278076aa65dd7a2838e5bcfc47ed
[백준] 16236번 : 아기상어 (bfs 심화 + vector< tuple<int, int,="" int=""> > 의 원소 출력 방… · shinbian11/ProblemSolv</int,>
…법 공부)
github.com
'Problem Solving > 백준' 카테고리의 다른 글
| [백준] 1450번 : 냅색문제 (냅색, DFS) (0) | 2022.01.25 |
|---|---|
| [백준] 1701번 : Cubeditor (KMP 알고리즘) (0) | 2021.01.16 |
| [백준] 2751번 : 수 정렬하기 2 & Merge Sort 에 대해서 (0) | 2020.10.30 |
| [백준] 16197번 : 두 동전 (0) | 2020.09.14 |
| [백준] 17413번 : 단어 뒤집기 2 (0) | 2020.08.27 |
