Henzee's Archive

문제 링크 문제 분석학생들 사이의 사이클을 발견한 뒤 방문 기록을 통해 중복 방문을 방지하고 사이클에 속하지 않은 학생 수를 출력하는 문제입니다.백준에서는 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..

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

문제 링크 문제 분석N×M 크기의 맵의 정보가 주어지면, (1,1)에서 (N,M)까지 가는 최단 거리를 구하는 문제이다.0은 이동할 수 있는 곳이고, 1은 이동할 수 없는 벽이다.단, 최대 1번만 벽을 부수고 이동할 수 있다.만약 도달할 수 없다면, -1을 출력한다. 문제 풀이 최단 거리를 구하는 문제임을 확인하고, 바로 BFS를 떠올렸다.다만, 추가 조건이 최대 한 번까지 벽을 부술 수 있다는 것이어서 벽을 부순 경우와 부수지 않은 경우를 나눠서 구해줬다. 1. 방문 배열을 2가지 경우로 나눠준다. (벽을 부수지 않은 경우, 벽을 부순 경우)2. 다음 방문 위치가 갈 수 있는 곳(0)인 경우, 방문3. 다음 방문 위치가 갈 수 없는 곳(1)이지만, 벽을 부순 적이 없으면 방문 이렇게 나누는 ..