Approach https://viyoung.tistory.com/331와 동일하다. [백준 5427번] [BFS] 불 Approach BFS를 2개 돌리면 된다. 시간 단위로 불과 상근이 모두 1칸씩 이동할 수 있으므로 상근이를 먼저 이동시키고 불을 이동시켜서 결과적으로 상근이가 경계선 밖을 넘는지 여부만 체크해주면 viyoung.tistory.com Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair pii; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; int r[1000][100..

Approach BFS를 2개 돌리면 된다. 시간 단위로 불과 상근이 모두 1칸씩 이동할 수 있으므로 상근이를 먼저 이동시키고 불을 이동시켜서 결과적으로 상근이가 경계선 밖을 넘는지 여부만 체크해주면 된다. 이미지로 가시화한 결과는 다음과 같다. https://m.blog.naver.com/kks227/220785747864 너비 우선 탐색(Breadth-First Search) (수정 2018-11-22) 자, 이제 빨리 DFS의 반대 개념인 BFS에 대해 배워보죠. BFS는 너비 우선 탐색(breadth-first sea... blog.naver.com 다만, 불의 경우에는 굳이 불인 경우에 대해서는 visited를 처리하지 않고 이동할 공간이 영역 내부이고 불에 해당하지 않으면 이동해주면 된다. 왜..

Approach https://viyoung.tistory.com/328와 완전히 동일~ [백준 7562번] [BFS] 나이트의 이동 Approach 2178번과 다를바가 없음. 다만, 이동하는 양상이 총 8개인점만 다르다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair pii;.. viyoung.tistory.com Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; class point { public: in..

Approach https://viyoung.tistory.com/326 이 문제를 3차원으로 확장한 것과 크게 다르지 않다. [백준 2178번] [BFS] 미로 탐색 Approach DFS가 아니라 BFS로 해야한다. DFS로 하게 되면 모든 가능한 케이스를 모두 조사해보아야 하는데, 그 경우는 $4^{NM}$이므로 시간초과가 난다. 추가적으로 큐에 여러번 들어갈 수 있는 가능성 viyoung.tistory.com Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; class point{ public: int z; int x; int y; point(){} point(i..

Approach 2178번과 다를바가 없음. 다만, 이동하는 양상이 총 8개인점만 다르다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; typedef pair pii; int r[300][300]; bool visited[300][300]; int move_x[8] = {-2, -2, -1, -1, 1, 1, 2, 2}; int move_y[8] = {-1, 1, -2, 2, -2, 2, -1, 1}; int main(void){ fastio; int t; cin >> t; while(t--){ memset(r, 0, sizeof(r)); memset(visited..

Approach 위 문제에서 나타나게 되는 그래프를 잘 관찰해보면 사이클이 반드시 등장하게 되는 것을 관찰할 수 있다. 즉 1개의 Component를 기준으로 사이클이 존재하고 해당 사이클에 속한 노드를 종점으로 하는 간선을 outdegree로 가지는 노드들이 존재하는 양상을 띄고 있다. 1개의 Component를 기준으로 사이클에 존재하는 것들은 서로서로 순환적으로 요구하고 있으므로 모두 다 버스에 타거나 전부 타지 말아야 한다. 따라서 해당 특성을 잘 고려하면 해당 component에서 버스를 탈 수 있는 인원은 사이클에 속한 사람 ~ 해당 component에 속한 사람이 된다. 그리고 최대 인원이 k명이라는 점을 잘 생각해보면 0/1 knapsack 문제와 비슷한 점을 발견할 수 있다. 왜냐하면 해..

Approach DFS가 아니라 BFS로 해야한다. DFS로 하게 되면 모든 가능한 케이스를 모두 조사해보아야 하는데, 그 경우는 $4^{NM}$이므로 시간초과가 난다. 추가적으로 큐에 여러번 들어갈 수 있는 가능성을 없애기 위해서 큐에 넣자마자 방문처리를 해줘야 한다. 이 부분때문에 처음에 메모리초과를 받았다. Code #include #define fastio ios_base::sync_with_stdio(0); using namespace std; typedef pair pii; char r[100][100]; int visited[100][100]; int move_x[4] = {-1, 1, 0, 0}; int move_y[4] = {0, 0, -1, 1}; int main(void){ fasti..

Approach DFS를 통해 트리의 높이를 추적하는 느낌이다. 다만, 사이클이 발생하는 경우에만 -1을 출력해주면 된다. 사이클이 발생하는 상황은 방문한 곳에 다시 방문을 시도하려고 할 때, -1을 출력해주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int n, m, p; int visited[100001]; int v[100001]; int r[100001]; int dfs(int c){ visited[c] = 1; if(v[c] == -1) return 0; int cur = r[v[c]]; int result = 0; if(!visited[cur]..