Henzee's Archive

바킹독 님의 시뮬레이션 강의를 듣고 해당 문제집에 있는 문제 중 하나여서시뮬레이션 문제라는 것을 알고 풀기 시작했다. 문제를 읽다보니 꽤나 복잡해서 여러 알고리즘을 사용해야 한다고 판단했다.먼저 전체 알고리즘을 짜봤는데,① 판 돌리기 (4^5가지 경우의 수)② 판 쌓기 (5!가지 경우의 수)③ 입구 선택하기 (8가지 경우의 수)④ 출구까지 최소 이동 거리 갱신하기 (5³가지 경우의 수) 4^5 × 5! × 8 × 5³ = 대략 1억 정도의 시간 복잡도를 가지므로 시간 제한에 걸리지 않는다. 판을 돌리고 쌓기 위해서 백트래킹을 사용하고,입구부터 출구까지 최소 이동 거리를 계산하기 위해 BFS를 사용한다. 중요한 점은,BFS 탐색 전에 입구와 출구가 막혀서 갈 수 없는 곳인 경우는 탐색하지 않도록 가지치기를..

문제 링크 문제 분석각 섬의 영역을 구분해주고 BFS 탐색을 통해 섬 간에 최단 거리를 구하는 문제입니다.시간 복잡도는 O(K * N²) (K = 섬 개수, N = 지도 크기) 입니다. 문제 풀이 입력받은 섬들의 영역을 구분합니다.구분할 때 고립되어 있지 않는 위치는 배열(lands)에 저장해줍니다.섬의 개수만큼 BFS 탐색을 하며 각 섬에서 다른 섬으로 가는 최단 거리를 구해줍니다.최단 거리의 최솟값이 정답이 됩니다.BFS 탐색 시 바다에 닿아있는 위치를 저장한 배열(lands)의 값을 큐에 넣고 탐색을 진행합니다.다른 섬을 만나면 저장된 거리를 반환하고 탐색을 종료합니다. 최종 제출 코드 #include #include #include #include #include #include ..

문제 링크 백준 2573번 - 빙산 (DFS) [C++] 99클럽 코테 스터디 10일차 TIL (DFS)백준 2573번 - 빙산 (골드 4) 문제 분석주어진 빙산의 높이 정보를 가지고 매 년마다 빙산이 녹으면 몇년 후 최초로 빙산이 2개 이상으로 분리되는지 찾는 문제이다. 만약, 모두 다 녹을 때까henzee.tistory.comDFS를 활용해 푼 같은 문제, 다른 풀이입니다. 문제 분석맞닿은 면이 바다일 경우 빙산을 녹이고, 두 개 이상으로 빙산이 분리되는 최초의 시간(년)을 구하는 문제입니다.주의할 점은 모든 면이 녹았는데도 분리되지 않는 경우는 0을 출력해야 합니다.또한, 빙산을 녹일 때 빙산의 정보가 저장된 맵(배열)에서 빙산을 그대로 녹이는 것이 아니라 새로운 배열에 녹인 ..

문제 링크 문제 분석학생들 사이의 사이클을 발견한 뒤 방문 기록을 통해 중복 방문을 방지하고 사이클에 속하지 않은 학생 수를 출력하는 문제입니다.백준에서는 DFS 문제로 카테고리가 분류되었는데 저는 바킹독 님의 알고리즘을 따라 BFS 개념으로 문제를 풀었습니다.시간 복잡도는 O(N) 입니다. 문제 풀이 각 노드를 따라가며 사이클을 찾습니다.탐색 중 state[cur] == x 인 경우는 현재 탐색에서 사이클이 발생한 것으로 간주해 사이클에 포함되는 노드를 마킹(state[cur] = CYCLE_IN) 합니다. 이미 방문한 노드인 경우(state[cur] != 0) 탐색을 종료합니다. 최종 제출 코드 #include #include #include #include #include #incl..

문제 링크 문제 분석불! 문제와 유사한 BFS 문제입니다.상근이가 불이 붙으려는 칸으로도 이동할 수 없기 때문에 큐에 넣는 순서를 고려해 풀어야 합니다.시간 복잡도는 O(T × W × H) 입니다. 문제 풀이 입력 시 불의 위치를 큐에 저장합니다. (*상근이의 위치는 입력이 끝난 뒤 저장해야 합니다.)불의 위치와 상근이의 위치를 넣고 탐색을 진행하며 탈출이 가능하면 걸린 시간을 출력하고 불가능 시 IMPOSSIBLE을 출력합니다. 최종 제출 코드 #include #include #include #include #include using namespace std;#define X first#define Y secondint dy[] = { 0, 1, 0, -1 };int dx[] = { 1..

문제 링크 문제 분석사방탐색이 아닌 팔방탐색을 해서 풀어야 하는 BFS 문제이며 시간 복잡도는 O(I²) 입니다. 문제 풀이 1. 시작 위치를 큐에 넣고 팔방탐색을 진행합니다.2. pop한 위치가 목적지라면 현재까지의 거리를 저장하고 탐색을 종료합니다. 최종 제출 코드 #include #include #include #include #include using namespace std;#define X first#define Y secondconst static int MAX = 300;int dx[] = { 1, 2, 2, 1, -1, -2, -2, -1 };int dy[] = { -2, -1, 1, 2, 2, 1, -1, -2 };string output;int T, I;bool map..

문제 링크 문제 분석기존의 토마토 문제에서 3차원 배열을 사용해서 풀어야 하는 것만 추가된 문제입니다.모든 탐색을 마친 후 토마토가 모두 익었는지 판별해서 날짜를 출력해야 합니다.시간 복잡도는 O(M×N×H) 입니다. 문제 풀이 입력 시 토마토면 큐에 넣어줍니다.BFS 탐색 전 모두 익었는지 확인 후 모두 익었으면 0을 출력합니다.BFS 탐색 중 while 문을 종료하기 전에 현재 날짜를 저장하고 탐색을 종료합니다.토마토가 모두 익었으면 날짜를 출력하고 익지 않았으면 -1을 출력합니다. 최종 제출 코드 위 알고리즘을 토대로 구현한 코드입니다.#include #include #include using namespace std;const static int MAX = 100;// 위 아래 왼..

문제 링크 문제 분석적록색약일 때 빨강과 초록을 같은 색상으로 생각하고 큐에 넣어주는 조건만 잘 추가해준다면 일반적인 BFS와 똑같은 방식으로 풀 수 있는 문제입니다.시간 복잡도는 O(N²) 입니다. 문제 풀이 방문 배열을 3차원으로 선언해 색약인 사람과 아닌 사람의 방문을 따로 처리합니다.BFS 탐색 시 id값에 따라 색약인 경우와 아닌 경우로 분류해줍니다.색약이 아닌 경우와 색약이더라도 색상이 파랑인 경우는 사방탐색 후 같은 조건을 만족하면 큐에 넣어 탐색을 진행합니다.색약인 경우 색상이 빨강과 초록이라면 두 가지 색상인 경우만 큐에 넣어 탐색합니다. 최종 제출 코드 위 알고리즘을 토대로 구현한 코드입니다.#include #include using namespace std;const ..

문제 링크 문제 분석 Flood Fill(플러드 필: 다차원 배열에서 특정 칸과 연결된 칸을 찾는 알고리즘)을 이용한 전형적인 BFS 문제입니다.M과 N의 최대 크기가 50이고 BFS로 문제를 해결하면 시간복잡도는 O(M × N)입니다. 문제 풀이 전체 맵을 한 번씩 탐색하며 배추가 심어져 있고, 이전에 방문 안한 곳이면 BFS 탐색을 하고 해당 조건에 들어갈 때마다 필요한 지렁이의 개수를 세도록 풀었습니다.BFS에서도 조건을 만족하는 위치를 큐에 넣고 사방탐색하며 배추가 심어져 있고 연결된 위치를 탐색 후 큐에 넣고 방문 처리를 해주어 중복 방문을 방지했습니다. 최종 제출 코드 위 알고리즘을 바탕으로 구현한 코드입니다. #include #include #include #include ..

문제 링크 문제 분석빌딩 가장 자리에서 시작해 열쇠를 줍고, 문을 열어 문서를 최대한 많이 훔치는 개수를 구하는 문제이다.열쇠를 줍고 나서 기존의 문을 다시 탐색을 해줘야 하는 부분이 어려워서 헤맸다. 문제 풀이 전체 탐색 시 가장 자리에서 갈 수 있는 부분(벽 or 방문한 곳 제외)을 탐색 후 큐에 넣어준다.만약 문일 경우 열쇠가 있으면 해당 위치를 큐에 넣고, 없으면 문의 위치를 저장한다.큐를 탐색하며 문서일 경우 개수 + 1을 하고, 열쇠일 경우 새로 주웠을 시 해당 열쇠의 문의 위치를 큐에 넣어 재탐색한다.다음 위치를 사방 탐색하며 갈 수 있는 경우는 큐에 넣고, 문일 경우 열쇠가 없으면 문의 위치를 저장한다.위 탐색을 모두 마친 뒤 새롭게 주운 열쇠가 없으면 전체 반복문을 종료하고 ..