hades

🥅 문제https://www.acmicpc.net/problem/1987 🔍 설계어떤 알파벳을 중복해서 방문할 수 없으므로, 알파벳에 대한 방문 여부를 visited에 저장한다. 말이 최대 연속해서 몇 칸을 지날 수 있는지 구하기 위해서는 DFS를 이용해야 한다. 지나는 경로 중간에 다른 방향으로 경로를 탐색하기 위해 백트래킹을 이용한다. 👊 풀이#include #include #include using namespace std;int r, c, result = 0;int dx[] = { -1,1,0,0 };int dy[] = { 0,0,-1,1 };vector> board(20, vector(20));vector visited(26);string s;void dfs(int cur_x, int cu..

🥅 문제https://www.acmicpc.net/problem/1167 🔍 설계가지가 1인 노드들에서 dfs를 이용하여 트리의 지름을 구하려고 했는데, 시간 초과가 발생하였다. 도저히 해결방법을 모르겠어서 레퍼런스 블로그를 참고하였다. 임의의 노드에서 가장 먼 노드를 구하고, 그 노드에서 가장 먼 노드를 구하면, 트리의 지름을 구할 수 있다고 한다.어떻게 이런 결과가 나오는지 공부해본다. 임의의 노드를 x라고 하고, x에서 가장 먼 노드를 y라고 하면, 3가지 경우가 있다.1) x가 트리의 지름의 양 끝 점 중 하나라면, x에서 가장 먼 노드인 y가 나머지 끝 점 중 하나가 되므로 y에서 가장 먼 노드(x)까지의 거리는 트리의 지름이 된다.2) y가 트리의 지름의 양 끝 점 중 하나라면, 당연하게 ..