문제 설명 & 접근 방식이 문제는 수빈이의 위치가 X-1, X+1, 2X로 이동할 수 있다는 점을 보아 BFS를 이용해야 함을 알 수 있다그리고 2차원 배열이 아닌 1차원 배열로 접근해야 한다 n을 BFS의 첫 시작점 인덱스로 하고 좌우 그리고 2배 지점을 탐색하면서기준점에 +1을 계산하여 걸린시간을 계산하여 저장한다탐색하는 인덱스가 k와 같아지면 동생을 찾은 것이므로 걸린 시간을 출력해주면 된다 코드#include #include using namespace std;int board[100002];int n,k;int main() { cin >> n >> k; queue q; board[n]=1; q.push(n); // 큐에는 인덱스를 넣어야함 while(!q.empty()..

문제 설명 & 접근 방식이 문제는 불과 지훈이가 상하좌우 네 방향으로 움직일 수 있으므로 BFS 문제임을 알 수 있고지훈이의 BFS와 불의 BFS를 따로 처리 해주어야 한다 우선 불의 BFS를 먼저 처리해서 불의 전파 시간을 구한다그 후 지훈이의 BFS를 돌리는데 만약 지훈이가 특정 구간을 x시간에 방문할 수 있는데x시간 이하 시간에 불이 붙는다면 지훈이는 접근이 불가능하게 된다이 부분을 if문과 continue로 처리해주면 된다 탈출하게된다면 지훈이의 도달 시간을 출력해주면 되고 탈출하지 못하면 IMPOSSIBLE을 출력한다탈출했다는 것은 탐색 구간이 범위 밖을 벗어났다는 의미이다 참고로 불이 없을 수 있고 불이 여러개일 수도 있다불이 없는 경우는 밑의 오류 부분에서 다룰 것이고불이 여러개인 경우 백..

문제 설명 & 접근 방식익은 토마토(1), 익지 않은 토마토(0), 토마토 없음(-1) 총 3가지 상태가 있으며익은 토마토는 하루가 지나면 상하좌우의 익지 않은 토마토들을 익게만든다총 몇일이 지나야 상자 안의 토마토가 모두 익는 지 구해야하는 문제다 이 문제는 토마토가 상하좌우 방향으로만 익어가고다 익는 최소일수를 구해야 하므로 BFS를 사용해야 함을 알 수 있다일수를 구하는 방법은 시작점으로부터의 거리를 계산하는 방식으로 구하면 된다 하지만 익은 토마토가 있는 지점이 여러 곳일 수 있어 익은 토마토가 위치한 곳을 모두 큐에 넣고 BFS를 돌리면 된다 코드#include #include #include #include #define X first#define Y secondusing namespace s..

문제 설명 & 접근 방식이 문제는 다차원 배열에서의 거리 측정 문제이다배열의 좌측 상단에서 시작해서 우측 하단으로 가는 최단 거리를 구해야 한다 BFS를 활용하여 시작점으로부터 연결된 모든 점들을 탐색하며 최단 거리를 구할 수 있다해당 칸이 접근 가능하여 방문 표시를 1로 남기는 것 대신에 시작점과의 거리를 남겨 구할 수 있다 #include #include #include #include using namespace std;#define X first#define Y secondstring board[502];int vis[502][502];int dx[4] = {1,0,-1,0};int dy[4] = {0,1,0,-1};queue> q;int n,m;int main() { ios::sync_wi..

문제 설명 & 접근 방식이 문제는 그림의 개수와 가장 넓은 그림의 넓이 총 2가지를 구해야 한다 우선 시작점이 하나로 정해져있는 것이 아닌 모든 구간이 시작점이 될 수 있으므로이중for문으로 시작점이 될 수 있는 지점을 찾아야 한다 그림의 개수는 while문을 빠져나왔다는 것이 그림이 완성됐다는 의미이므로while문을 탈출했을 때 카운트를 해주면 된다 그림의 넓이는 while문을 돌 때 해당 칸이 접근가능하여 방문표시를 남길 때 카운팅을 같이 해주어 구하면된다그림이 완성될 때마다 max함수를 이용하여 그 전의 가장 넓었던 그림과 지금 완성된 그림 중 어느 것이 더 큰지 구한다 코드// Online C++ compiler to run C++ program online#include #include #inc..

들어가며오늘은 알고리즘에 조금이라도 관심이 있고 코딩테스트를 준비하는 사람이라면누구나 알만한 주제인 BFS에 대해 알아볼 것이다BFS는 코딩테스트 단골 유형으로 출제되고 응용 문제도 많아서BFS 코드의 기본 틀은 어느정도 암기를 해야 문제푸는데에 수월할 것이다 BFS란BFS는 Breadth First Search의 약자로 너비 우선 탐색이라는 의미를 가진다주어진 속성을 만족하는 노드를 찾기 위해 트리를 탐색하는 알고리즘이다. 너비 우선 탐색이라는게 무슨말인지 의문을 가질 수 있다트리 구조에서 가로 방향을 너비라고하고 세로 방향을 깊이라고 한다너비 우선 탐색은 같은 깊이의 가로 방향의 노드들을 전부 다 탐색하고그 다음 깊이로 내려가 또 같은 깊이의 노드들을 탐색하는 방식이다 위의 사진을 예시로 들면1 ->..

문제 설명 & 접근 방식이 문제는 백준 괄호 문제와 비슷한 방식으로 풀 수 있는데A를 "( )" 로 보고 B를 "[ ]" 로 이해하면 된다스택의 top의 값과 문자를 비교하여 소거해 나가면 되는 문제이다 접근은 비슷한 방식으로1. 입력받은 문자열을 순회하면서 스택이 비어있지 않고 짝이 맞으면(같은 문자면) pop하고2. 그렇지 않으면 현재 문자를 push 해준다3. for문 순회가 다 끝나고 스택이 비어있으면 좋은 단어이므로 카운트한다 코드#include #include #include #include using namespace std;int main() { int n; string s; int cnt = 0; cin >> n; for(int tmp=0; tmp> s;..

문제 설명 & 접근 방식이 문제는 백준 4949번이랑 매우 유사한 문제이다 어떻게 보면 중괄호" [ ] " 가 없어서 더 쉬운 문제라고 생각한다 접근 방식도 똑같이1. 열린 괄호 나오면 스택에 추가2. 스택이 비어있다면 짝이 없다는 것이므로 탈락3. 비어있지 않다면 짝이 무조건 맞으므로 pop4. 2~3과정 끝났는데 스택에 괄호 남아있으면 탈락 없으면 통과 코드#include #include #include #include using namespace std;int main() { int n; string s; bool isValid = true; cin >> n; for(int tmp=0; tmp> s; stack st; isVa..

문제 설명 & 접근 방식" ( " 는 " ) " 랑만 " [ " 는 " ] " 랑만 맞춰져야하고 한 문장이 완벽히 다 괄호 쌍들이 맞아야 균형잡힌 문자열인 것이다닫는 괄호가 나왔을 때 짝을 맞추어 소거해가는 방식으로 풀어야된다고 봤으므로 스택을 사용해야한다고 생각했다 접근 방식으로는1. 여는 괄호가 나오면 우선 스택에 push한다2. 닫는 괄호가 나온 경우 2-1 스택이 비어있다면 탈락 2-2 스택의 top이 짝이 안맞으면 탈락 2-3 스택의 top이 짝이 맞으면 pop3. 1~2 과정이 끝났는데 스택에 괄호가 남아있으면 탈락 없으면 통과 이 규칙으로 구현해주면 된다 코드#include #include #include #include using namespace std;int main() { ..

#include #include #include using namespace std;int main() { int n,m,x; cin >> n >> m; int cnt=0; vector v2; deque d; for(int tmp=1; tmp> x; v2.push_back(x); } for(int tmp : v2) { int count = 1; for(int tmp2 : d) { if(tmp2 == tmp) break; else count++; } ..