전체 글
[C++] BOJ 17071 / BFS (숨바꼭질 5, 특성 파악하기)
문제 분석 https://www.acmicpc.net/problem/17071 이전 숨바꼭질 문제에서 동생의 움직임을 추가한 문제이다. 난이도는 Solved.ac 기준 Gold1로 매우 어려운 축에 속한다. 2019 라인플러스 상반기 인터 채용 문제 중에 마지막 문제를 변형시킨 문제이며, 불합을 결정하는 난이도이다. 일단 중요하게 봐야할 부분은 n이 50만으로 크며, 시간 제한이 0.25초라는 점이다. 적절한 분석 및 계획 없이 무턱대고 BFS를 구현하면 시간초과가 뜨기 쉽다. 해결 방법 이런 문제를 접하면, 가장 먼저 중요한 특성을 파악하려 노력해야한다. 이 문제에서 가장 중요한 특성은, 어떤 점 x에 t초에 도달할 수 있다면, t+2, t+4, t+6,..에도 x에 도달할 수 있다는 것이다. 즉, 여..
[C++] BOJ 13913 / BFS (숨바꼭질 4, 배열 꼬리물기 적용)
문제 분석 https://www.acmicpc.net/problem/13913 바로 이전에 포스팅한 숨바꼭질 3 (BOJ 13549) 에서 출력 값을 추가 시킨 문제이다. 수빈이가 동생을 잡았을 때 어떤 최단 경로를 통해 잡았는지 또한 출력해줘야 한다. 이런 유형의 문제는 낯설어서 처음엔 vector를 써서 모든 좌표 값에 대해 추적을 진행하려고 했지만 이내 시간 제한 때문에 불가능 함을 깨닫게 되었다. 해결 방법 배열을 하나 더 선언하여서, 꼬리물기를 진행하면 된다. 쉽게 설명하자면, 배열을 연결리스트처럼 활용하였다. queue에 push할 때, 이 좌표가 파생된 좌표를 trace 배열에 인덱스를 활용하여 넣어준다. 말로 설명하기가 힘들어서 코드를 보며 이해했으면 좋겠다. trace[] 라는 이름으로 ..
[C++] BOJ 13549 / BFS (숨바꼭질 3)
문제 분석 https://www.acmicpc.net/problem/13549 숨바꼭질1 (BOJ 1697) 의 변형 문제이다. 해당 문제와 다른 점은 2*X 이동을 하는 순간이동에 걸리는 시간이 "0초" 라는 점이다. 해결 방법 단순히 2*X 이동 할 때는 dist를 이전dist에서 1을 더해주지 않으면 된다. (1초가 아닌 0초기 때문) 코드 #include #include #include int dist[200001]; using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); queue q; int n,k; cin >> n >> k; q.push(n); dist[n] = 1; while(!q.empty()) { int flag=0..
[C++] BOJ 2146 / BFS (다리 만들기)
문제 분석 https://www.acmicpc.net/problem/2146 solved.ac 기준으로 골드3 문제에 처음 도전해봤다. 지도에 섬이 주어지며, 섬 간에 최소 거리를 구하는 문제이다. 해결 방법 문제를 보자마자, 3가지 절차를 정리했다. 1. 섬 좌표 입력을 받은 후, BFS를 돌면서 섬마다 번호를 다르게 부여한다. (본인 코드에서는 "island"변수 활용) 2. 또 다른 큐에 들어가는 것은 주변에 "0"이 있는 육지이다. (본 코드에서는 "q2" 활용) 3. 또 다른 큐(q2)를 pop 해가며 다른 섬에 닿을 때 까지 BFS를 동작시킨다. 4. 1번부터 3번까지 반복 진행하며 최솟값을 출력한다. 코드 #include #include #include #include #define X fi..
[C++] BOJ 5427 / BFS (불 따로 사람 따로)
문제 분석 https://www.acmicpc.net/problem/5427 한 쪽으로 영향을 미치는(불이 사람에게) 문제이다. 불이 사람보다 먼저 탐색하여 지나간 길을 사람이 지나갈 수 없다. 서로에게 영향을 미치는 문제는 백트래킹을 사용해야 하며, 해당 문제는 추후에 다루도록 하겠다. 해결 방법 BFS를 불 먼저 시간(거리)를 계산하여 기록하고, 사람을 후에 계산하면서 불 보다 늦게 지나가는(거리가 더 먼) 지점은 벽 처럼 큐에 넣지 않도록 continue하는 조건을 추가하면 된다. 코드 #include #include #include #include using namespace std; #define X first #define Y second int board[1001][1001]; int dis..
![[C++] BOJ 2667 / BFS (문자열 파싱 접근)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FnCatS%2FbtracYZzB8c%2FZN12LGRn8HWK3k2kkkjmCK%2Fimg.png)
[C++] BOJ 2667 / BFS (문자열 파싱 접근)
문제 분석 https://www.acmicpc.net/problem/2667 BFS로 탐색하며 각 그룹의 개수를 계산하여 오름차순으로 정렬하여 출력하는 문제이다. 예제로 주어진 입력을 보면 다른 문제와는 다르게 "문자열"로 주어진 것을 알 수 있다. 이에 주의하여 입력을 처리해야 한다. 해결 방법 한자리 숫자의 문자는 '0'을 빼주면 ascii 코드로 계산되어 숫자로 변환된다. 이를 응용하여 입력 받으면 된다. 코드 #include #include #include #include #include #include #include using namespace std; #define X first #define Y second int board[25][25]; int vis[25][25]; int dx[4]=..
[C++] BOJ 2583 / BFS (sort 사용)
문제 분석 기본 BFS 문제와 기본 틀은 같다. 영역의 크기와 분리된 영역의 개수를 BFS 를 통해서 구하면 된다. 해결 방법 칠한 부분을 "벽"이라고 가정한 후 나머지 영역에서 BFS를 적용하면 된다. 주어지는 좌표 값이 왼쪽 모서리의 좌표와 오른쪽 모서리의 좌표가 주어지는데, 이를 2차원 배열에 행 열로 넣으면 그림이 거꾸로 나온다. 하지만 영역의 크기를 계산하면 되는 문제이기 때문에 상관없다. 영역의 크기를 "오름차순"으로 정렬하여 출력하라는 조건이 주어졌기 때문에 Sort 함수를 사용하였다. 코드 #include #include #include #include #include using namespace std; #define X first #define Y second int board[101]..
[C++] BOJ 7569 / BFS (3차원 배열, tuple 사용)
문제 분석 해당 문제는 Z축이 포함된 3차원에서의 BFS를 계산하는 것이다. 해결 방법 세로 칸 수를 X, 가로 칸 수를 Y, 높이를 Z 로 하여 3차원 배열으로 접근한다. 코드 #include #include #include using namespace std; int board[101][101][101]; int dx[6]={1,0,-1,0,0,0}; int dy[6]={0,1,0,-1,0,0}; int dz[6]={0,0,0,0,1,-1}; int main() { int n,m,h,status,max=1; queue q; cin >> m >> n >> h; for(int k=0;k
[C++] BOJ 1697 / BFS (fill, range based for 사용)
문제 분석 BFS 문제는 2차원 배열로 주어지는것이 흔한데, 이 문제는 특이하게 1차원인데다가, "상 하" 이동 없이 "좌 우"로만 이동하기 때문에 BFS를 떠올리는 것이 힘들었다. 해결 방법 1차원 배열에서 BFS를 돌리면서, 동생의 위치와 인덱스가 겹칠 때의 distance 값을 출력한 후 종료하면 된다. 코드 #include #include using namespace std; int dist[100001]; int main() { ios::sync_with_stdio(0); cin.tie(0); queue q; int n,k; fill(dist, dist+100001, -1); cin >> n >> k; if(n == k) { cout = 100001) continue; if(dist[nx] !=..
[C++] BOJ 7576 / BFS 응용(시작점이 여러 개)
문제 분석 BFS 기초 문제를 풀다보면 만나는 문제이다. 문제의 조건에 토마토의 개수가 1개로 고정된다는 말이 없으므로, 토마토의 개수가 여러 개 일 수 있으며, 이말은 즉 BFS를 돌릴 때의 시작점이 여러개라는 뜻이다. 해결 방법 시작점이 여러 개인 BFS의 경우, 모든 시작점을 큐에 넣고 BFS를 돌면 자연스럽게 거리가 구해진다. 코드 #include #include #include using namespace std; #define X first #define Y second int board[1001][1001]; bool vis[1001][1001]; int dx[4] = {1,0,-1,0}; int dy[4] = {0,-1,0,1}; int main() { ios::sync_with_stdio..