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]..

Approach Component 개수를 물어보는 문제이다. 기본적인 접근 방법은 다음 문제와 거의 유사하다. https://viyoung.tistory.com/317 [백준 1012번] [DFS / BFS] 유기농 배추 Approach 연결 요소(Component)의 개수를 묻는 문제이다. 배추가 심어져 있는 곳에 대해서 방문하지 않았다면 DFS / BFS를 돌리고 component의 개수를 1 증가시켜 주면 된다. Code #include #define fastio ios_b.. viyoung.tistory.com 다만 이 문제의 경우는 연결 여부가 이미 결정되어있는 반면, 이 문제의 경우는 높이를 변화시키면서 component 개수의 변화를 보고 그 중 최댓값을 출력해준다는 점에서만 차이가 존재한다..

Approach 처음에는 DFS를 돌 되, 스택을 활용해서 자신보다 밑에 있는 element 들은 방문할 수 있다는 점을 활용해서 component별로 처리하려고 했는데 사이클이 존재할 수 있는 측면때문에 실패하였다. 물론 코드를 잘(?) 짜면 가능할 것 같기도 하다. 기본적인 접근 방법은 모든 노드들에 대해서 dfs를 돌면서, 방문할 수 있는 노드를 찾아나가면 된다. 다만, 유의할 지점이 사이클이 존재할 수 있기 때문에 자기 자신으로 돌아오는 간선이 있으면 따로 체크해주어야 한다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int r[100][100]; int ..

Approach Component 개수를 물어보는 문제이다. 적록색약이 아닌 경우와 적록색약인 경우에 대해 각각 component 개수를 따로 구해주면 된다. 주의할 지점은 적록색약의 경우 R, G를 구분하지 못한다는 점이다. 따라서 R과 G사이에 이동할 수 있다는 점만 고려해주면 된다. (모듈러 연산을 통해 쉽게 처리하였다.) Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; // 0 : red, 1 : blue, 2 : green int r[101][101]; int visited[101][101]; int n; int move_x[4] = {-1, 1, 0, 0};..

Approach 사실상 이 문제와 거의 동일하다. https://viyoung.tistory.com/317 [백준 1012번] [DFS / BFS] 유기농 배추 Approach 연결 요소(Component)의 개수를 묻는 문제이다. 배추가 심어져 있는 곳에 대해서 방문하지 않았다면 DFS / BFS를 돌리고 component의 개수를 1 증가시켜 주면 된다. Code #include #define fastio ios_b.. viyoung.tistory.com 단, 유기농 배추 문제와 달리 이동할 수 있는 노드를 직접적으로 제시하지 않고 이동할 수 없는 노드들을 제시했다는 점에서만 차이가 존재한다. 근본적인 접근 방법은 완전히 동일하다고 할 수 있다. 결과적으로 Component 개수를 물어보는 문제라고 ..