BFS

[C++] 백준 19238번 스타트 택시

19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 수록 문제. 구현 + 시뮬레이션 + 그래프 탐색 알고리즘으로 풀 수 있다. 문제 해석 택시의 조건은 다음과 같다. 목적지에 도착 시, 연료가 충전된다. 연료가 바닥날 경우 업무가 끝난다. 택시는 빈 칸의 상, 하, 좌, 우로 이동하며 특정 위치에 최단 경로로만 이동한다. 연료는 이동 한 칸마다 1이 소모된다. 다른 조건들은 다음과 같다. M명의 승객을 태우는 것을 목표로 한다. 활동 영역은 ..

[C++] 백준 6593번 상범 빌딩

6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 삼차원 배열로 풀 수 있는 그래프 탐색 문제. 삼차원 배열 초기화, 출력만 잘 맞춰주면 쉽게 풀 수 있다. /* * 백준 6593번 상범 빌딩 * https://www.acmicpc.net/problem/6593 * 그래프 탐색 이론 - 너비 우선 탐색(BFS) */ #include #include #include using namespace std; struct Point { int l; int r; int c; }; Point startPoint; int buil..

[C++] 백준 3055번 탈출

3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 4179번 불! 과 같은문제 [C++] 백준 4179번 불! 그래프 탐색 문제. 최근에 이런 비슷한 문제인 3055번 탈출이라는 문제를 풀다가 실패했었다. 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 kimyunseok.tistory.com 그래프 탐색을 두 종류로 나누어서 진행해주면 된다. 저 때 풀이와 완전 다르게 풀었다. 문제 풀이 다음과 같은 조건이 있다. 마법을 부려 숲에 홍수를 낸다. 1마리인 도치가 비버굴..

[C++] 백준 2589번 보물섬

그래프 탐색 문제. 오랜만에 풀어보는 알고리즘 문제라 그런지 머리가 잘 안 돌아갔지만 그래프 탐색이란 것을 알고 쉽게 풀 수 있었다. 문제풀이 땅 - 땅으로 이동하는 거리중 가장 긴 거리를 찾으면 된다. 돌아가면 안되고 최단거리 기준이므로 DFS는 안되고 BFS로 탐색해야한다. 이 기준대로만 구현하면 쉽게 풀 수 있다. /* * 백준 2589번 보물섬 * https://www.acmicpc.net/problem/2589 * 그래프 탐색 이론 - 너비 우선 탐색, 브루트 포스 */ #include #include #include #include using namespace std; int height, width; char board[51][51]; bool visit[51][51]; vector visi..

[C++] 백준 12851번 숨바꼭질 2

그래프 탐색 문제. BFS 너비 우선탐색을 통해서 풀면 되는 문제다. 조건이 꽤 까다로운 문제다. 다른 그래프 탐색 문제들처럼 풀면 메모리 초과가 난다. 문제풀이 예전에 숨바꼭질1을 풀었었는데, 그 때는 그냥 가장 빠르게 목적지에 도달한 경우 몇 초인지만 알면 되는 문제였다. 이 문제는 가장 빠르게 목적지에 도달한 경우가 몇 초이고, 그 시간대로 가는 경우가 몇 가지가 존재하는지 출력하면 된다. 조건은 짜기 나름이므로, 코드 전문을 보고 틀린 이유만 정리하겠다. /* * 백준 12851번 숨바꼭질 2 * https://www.acmicpc.net/problem/12851 * 그래프 탐색 이론 - 너비 우선 탐색(BFS) */ #include #include using namespace std; int s..

[C++] 백준 17142번 연구소 3

17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 에 수록된 문제. 골드 4 문제이며 연구소 문제의 후속작(?)인 것 같다. 연구소 문제는 골드 5에 정답률도 55%를 기록하고 있지만, 이 문제는 골드 4에 정답률이 25%를 기록하고 있다. 연구소 문제는 그래프 탐색 이론 문제이고, 너비 우선 탐색(BFS)을 통해서 푸는 문제이다. 사실 왜 맞았는지 잘 모르겠다. TC들이 제대로 나오지 않길래, 조건을 조금 수정해서 TC들이 잘 나와서 제출했더니 맞았습니다!! 가 나와버렸다... 한번 글..

[C++] 백준 16234번 인구 이동

구현 / 시뮬레이션 / 그래프 탐색 - 너비 우선 탐색 문제. 인구 이동이 같은 날에 동시에 일어날 수 있다는 것을 생각하고 풀어야 한다. 위 부분을 생각하지 못해서 게시판을 참고하면서 왜 테스트 케이스가 다르게 나오는지 확인했던 문제였다. 문제풀이 N x N 크기의 땅이 있을 때, 인접한 두 땅의 인구 수 차이가 L이상, R이하라면 연합을 한다. 그리고 연합 땅들의 인구 수를 (연합의 총 인구수 / 연합의 칸의 개수)로 만든다. 사실 BFS로 풀면 어려운 조건은 없다. 그러나 유의해야 할 점이 있다. 위에서 말한 것 처럼, 우리는 인구 이동의 수가 아닌, 며칠동안 인구 이동이 지속되냐 이다. 따라서 같은 날에 인구 이동이 2번, 3번, 4번, ... 이렇게 발생해도 결국 우리는 며칠동안 지속되는지만 확..

[C++] 백준 4179번 불!

그래프 탐색 문제. 최근에 이런 비슷한 문제인 3055번 탈출이라는 문제를 풀다가 실패했었다. 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 아예 조건이 똑같던 문제였는데 불! 문제는 풀었었다. (오히려 정답률은 탈출이 높다..뭐지..?) 다른 사람들 풀이를 보니 조금 쉽게 접근한 거 같았다. 시간도 내가 훨씬 많이 걸리고 있었다. 다른 사람들 코드를 봐도 크게 다른 점은 못 찾았다. 아마 priority_queue를 custom해서 쓰는데, 이게 문제인 것 같았다. queue 자료구조만 사용해서 풀어도 풀 수 있는 문..

[C++] 백준 16236번 아기 상어

구현 / 시뮬레이션 + BFS(너비 우선 탐색) 문제. 테스트 케이스가 상당히 많고 잘 돼 있어서 디버깅을 하다보면 맞출 수 있다. 처음에 4번째 테스트 케이스가 자꾸 다른 값(60이 아니라 56)이 나와서 뭐가 잘못됐는지 모르겠어서 백준 게시판에 봤더니 고려해 주지 못한 부분이 있었다. 아마 테스트 케이스들만 올바른 방향으로 통과한다면 맞출 수 있을 것이다. 문제풀이 아기상어는 다음과 같은 조건을 갖는다. 이동은 상, 하, 좌, 우 방향으로 가능하다. 이동하는데는 1초의 시간이 소요가 된다. 처음 아기상어의 크기는 2이고 자신의 크기만큼 물고기를 먹으면 크기가 증가한다. 자신의 크기보다 큰 물고기가 있는 곳은 지나가지 못하고, 같은 물고기가 있는 곳은 지나가기는 가능하며, 더 작은 물고기가 있는 곳은 ..

[C++] 백준 2206번 벽 부수고 이동하기

그래프 탐색 문제. 최단 거리를 탐색하는 문제로, BFS를 응용해서 풀면된다. 조건을 따지지 못해서 검색을 했는데, 코드를 약간 수정해서 맞출 수 있었다. 처음에 이 문제를 접근했을 때 N x M의 맵이고, 벽은 1이고 땅은 0이다. 그리고 상, 하, 좌, 우를 이동할 수 있다. 1로 된 곳 중 하나를 부숴서 갈 수 있다. 나는 다음과같은 조건들을 고려했다. BFS로 점들을 이동하며, 내가 이 점에 왔을 때 벽을 부수고 온 것인지 아닌지를 고려했다. 만일 이전에 벽을 부수고 왔다면, 이번 정점에서는 벽을 가지 못하도록 했다. 이전에 벽을 부순적이 없다면, 벽을 부쉈다는 것을 기록하고 해당 벽을 방문한다. visit 2차원 배열을 만들어서 해당 지점을 방문한 것을 저장했다. 빨간색으로 칠한 이유는 저 부분..