BFS
-
[BOJ] #16234 _ 인구 이동Problem Solving/BOJ 2019. 10. 22. 19:40
[인구 이동] https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 www.acmicpc.net bfs를 이용하는 문제이다. move_q라는 큐를 이용하여 인구 차이가 L 이상 R이하인 곳을 모두 알아내었고, 국경선..
-
[BOJ] #2468 _ 안전 영역Problem Solving/BOJ 2019. 8. 28. 20:03
[안전 영역] https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어 www.acmicpc.net bfs나 dfs를 이용하여 안전한 구역의 개수를 세는 문제이다. [ 소스 코드 ] #include #include #in..
-
[SWEA] #5656 _ 벽돌 깨기Problem Solving/SWEA 2019. 8. 4. 10:28
[벽돌 깨기] https://swexpertacademy.com/main/code/problem/problemDetail.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 벡터를 사용하여 벽돌을 세로가 아닌 가로로 저장하고, 가장 끝에 있는 값을 깨는 방법으로 구현하였다. (erase를 사용하여 가운데 값을 삭제해도 앞으로 땡기는 작업을 하지 않기 위해 벡터 사용) 하지만, 직관적으로 보기에는 배열을 이용하는게 좋은 것 같다..;; 깰 수 있는 모든 경우의 수를 다 돌려 가장 벽돌이 적게 남은 경우를 출력하였다. 모든 경우의 수를 하지 않는 방법을 생각하다가,,, 제한 시간이 3초인 것을 보고 모든 경우의 ..
-
[SWEA] #5644 _ 무선 충전Problem Solving/SWEA 2019. 8. 4. 10:17
[무선 충전] https://swexpertacademy.com/main/code/problem/problemDetail.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com bfs를 이용하여 BC의 충전 범위 만큼 성능 값을 맵에 저장한다. 이 때, 사용자는 두명이기 때문에 BC의 가장 큰 두개의 값만 저장하고 있으면 된다. (BC가 4개가 겹칠 경우에 큰 성능 2개를 저장) 미리 맵에 마름모 꼴로 성능 값을 저장해두고, 두명의 사용자가 움직일 때, 맵에 저장된 값을 더해주면서 총 충전량을 구한다. [ 소스 코드 ] #include #include #include #include using namespace ..
-
[SWEA] #1249 _ 보급로Problem Solving/SWEA 2019. 7. 17. 07:00
[보급로] https://www.swexpertacademy.com/ SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 처음에는 dp로 풀 수 있을 것이라고 생각하였다. 그러나, 아래와 같이 돌아가야하는 경우에 내가 생각한 dp로 풀면 올바른 답을 얻을 수 없다. dp의 결과로는 7이 최소 시간으로 구해지나, 최소 시간은 6이다. 이와 같은 경우를 고려하기 위해 bfs를 사용하였다. 지도에서 bfs로 그냥 탐색하면 시간이 너무 오래 걸리기 때문에 불필요한 탐색은 줄여야한다. dp의 결과를 기준으로 두고, dp의 값 보다 작은 경우에만 bfs로 탐색하여 최소 시간을 구하는 방식으로 구현하였다. (다른 사람의 풀이를..