문제 (https://www.acmicpc.net/problem/16234)
16234번: 인구 이동
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모
www.acmicpc.net
DFS로 해결한 문제!
처음엔 문제를 제대로 이해하지 못하고 너무 어렵게 접근해서 삽질했다 ㅠㅠㅠㅠ
하지만.. 정신 차리고 풀어보니 간단했다.....😑
예제가 5개 있는데 예제 4, 예제 5를 직접 구해보면 이해가 잘 된다!
dfs를 진행하며 국경선이 열리는 곳의 좌표들을 v(vector)에 넣어준다.
- v의 size가 1이면? 해당 좌표에서는 국경선이 열리는 곳이 없는 것
- 아니면? 1. dfs를 돌며 구한 인구의 합으로 새로운 인구수를 구한다. 2. (v에 들어있는 좌표들, 변경할 값)을 record(vector)에 넣어준다.
가능한 dfs를 모두 진행 후 -> record에 있는 값들로 값을 변경해줌
while문 탈출 조건 (더 이상 인구 이동이 없는 경우)
- v의 size가 1일 때마다 증가시켜준 cnt 변수 값이 n * n과 같을 때
출력값
- while문을 한 번 돌 때마다 증가시킨 변수 값
[소스코드]
'ALGORITHM > BOJ' 카테고리의 다른 글
| [BOJ] 12904번 A와 B (C++) (0) | 2021.11.24 |
|---|---|
| [BOJ] 2866번 문자열 잘라내기 (C++) (0) | 2021.11.18 |
| [BOJ] 20055번 컨베이어 벨트 위의 로봇 (C++) (0) | 2021.10.22 |
| [BOJ] 3055번 탈출 (C++) (0) | 2021.10.14 |
| [BOJ] 10026번 적록색약 (C++) (0) | 2021.10.14 |