궤도

문제 풀이 이런 그래프가 있다고 하자. 이 그래프를 탐색할 시 선택의 순간이 2번 있다. 바로 1번 정점과 2번 정점에서이다. 1번 정점에선 2번 또는 3번 정점으로 갈 수 있다. 2->3의 순서로 큐에 넣어도 되고 3->2의 순서로 큐에 넣어도 된다. 2번 정점에선 마찬가지로 4->5 또는 5->4의 순서로 큐에 넣을 수 있다. 이 순서는 순전히 처음에 그래프의 연결된 정점을 어떤 순서로 저장했느냐에 따라 달라진다. 1->2, 3으로 저장했다면 2->3의 순서로 큐에 들어갈 것이고 1->3, 2로 저장했다면 3->2의 순서로 큐에 들어갈 것이다. 입력된 방문 순서에 따라 정점의 저장 순서를 바꿀 것이다. 먼저 인접 정점의 정보를 이렇게 저장했었다고 가정하자. 1->2, 3 2->1, 4, 5 3->1,..

문제 풀이 굉장히 비효율적인 방법으로 풀었는데 시간초과가 나지 않았다. 문제를 풀고나서 효율적으로 작성한 코드를 몇개 봤지만 도통 이해가 되지 않아서...강해져서 돌아와야겠다. 아무튼 내가 한 비효율적인 방법은 정점의 개수만큼 dfs를 실행한 것이다. 최대 입력이 3,000이라 시간초과가 발생할 것이라고 생각했는데 그렇지 않았다. 사실 다른 효율적인 방법을 나름 시도해봤지만 영 제대로 풀리지가 않았다. myunji.tistory.com/350 [백준] 4803번 : 트리 문제 풀이 트리의 가장 큰 특징은 사이클이 없단 것이다. 이러면 안된다는 뜻이다. 그래서 이번에 새로 방문할 정점이 이전에 방문한 정점인지, 그래서 사이클이 형성됐는지 확인해야 한다. 근 myunji.tistory.com 이 문제에서 그..

문제 풀이 myunji.tistory.com/350 [백준] 4803번 : 트리 문제 풀이 트리의 가장 큰 특징은 사이클이 없단 것이다. 이러면 안된다는 뜻이다. 그래서 이번에 새로 방문할 정점이 이전에 방문한 정점인지, 그래서 사이클이 형성됐는지 확인해야 한다. 근 myunji.tistory.com 이 문제에서 사이클을 찾는 방법을 배웠다. 이번에도 똑같은 방법으로 dfs를 하면서 사이클을 찾으면 된다. 그냥 사이클 여부만 확인하면 되는거라 간단한 문제다. 소스코드 #include #include #include #include using namespace std; vector board; //문자, 방문여부 int N, M; bool isCycle; pair dir[4] = {{-1, 0}, //상 ..

문제 풀이 트리의 가장 큰 특징은 사이클이 없단 것이다. 이러면 안된다는 뜻이다. 그래서 이번에 새로 방문할 정점이 이전에 방문한 정점인지, 그래서 사이클이 형성됐는지 확인해야 한다. 근데 dfs를 많이 사용해봤다면 이런 생각이 들 수 있다. dfs는 가능한 정점을 찾을 때 visited를 체크하는데 그럼 2가 이미 visited 였을테니 4->2가 될리 없지 않나? 그래서 연결된 정점을 찾고 dfs를 실행할 때는 visited를 체크하지 않는다. 근데 이러면 또 이런 생각이 들 수 있다. 그럼 1->2를 가고도 2->1이 탐색 가능해지는거고 이럼 무한루프가 되는거 아닐까? 그렇기 때문에 dfs의 현재 정점과 더불어 이 정점이 어떤 정점에서 이어져온 것인지 직전 정점도 저장한다. 소스코드 #include..

문제 풀이 inorder는 (왼쪽 트리)(루트)(오른쪽 트리) 순서로 탐색한다. postorder는 (왼쪽 트리)(오른쪽 트리)(루트) 순서로 탐색한다. 1991번의 이 트리를 숫자로 바꿔보자. inorder 순회는 4 2 1 5 3 6 7 이고 postorder 순회는 4 2 5 7 6 3 1 이다. postorder 순회의 맨 마지막 값인 1(=A)가 트리의 최상위 root 노드인 것을 확인할 수 있다. 1을 기준으로 inorder를 나눠보면 (4 2)(1)(5 3 6 7)이 된다. 4(=D), 2(=B)는 A의 왼쪽 트리 요소이고, 5(=E), 3(=C), 6(=F), 7(=G)는 A의 오른쪽 트리 요소다. 루트노드를 기준으로 왼쪽, 오른쪽 트리로 분할해나가며 트리를 구하면 된다. 사실 preord..

문제 풀이 그림에 답이 있다. 오른쪽 그림의 회색 점들 중에서 아무거나 하나를 찍어보자. 그리고 그 회색점에서 가장 멀리있는 점을 찾아보자. 어떤 회색점을 골라도 두 개의 파란점 중 하나가 선택될 것이다. 그렇다면 아무 점이나 하나 고르고, 그 점과 가장 먼 점을 고르면 그건 지름을 구성하는 2개의 점 중 하나인 것이다. 그러면 이렇게 구한 점 하나에 대해 또 가장 멀리 있는 점을 고르면 그 점은 지름을 구성하는 또다른 점인 것이다. 그 둘 사이의 거리가 지름이다. 이걸 구현하기 위해 dfs를 2번 사용할 것이다. 첫번째 dfs로 지름을 구성하는 점 중 하나를 찾고, 두번째 dfs로 트리의 지름을 찾는다. 거리를 dfs로 구해도 되는지 걱정될 수도 있다. 근데 트리의 특징 중 하나는 특정 정점 2개를 연..

문제 풀이 굳이 안그래도 될걸 억지로 어렵게 만들었다는 느낌이 드는 문제다. myunji.tistory.com/345 [백준] 1504번 : 특정한 최단 경로 문제 풀이 반드시 거쳐야 하는 정점이 B, C라고 하자. 이 둘을 거친 최단 경로는 1->B->C->N 또는 1->C->B->N일 것이다. 이걸 구하기 위해선 다익스트라 알고리즘을 3번 실행해야 한다. 1에 대하여 실행 myunji.tistory.com 논리는 이 문제랑 같다. 일단 s->t 최단 거리를 구한다. 만약 s->g->h->t 또는 s->h->g->t 의 최단거리와 s->t와 같다면 목적지가 될 수 있다. 소스코드 #include #include #include #include #include #include using namespace..

문제 풀이 반드시 거쳐야 하는 정점이 B, C라고 하자. 이 둘을 거친 최단 경로는 1->B->C->N 또는 1->C->B->N일 것이다. 이걸 구하기 위해선 다익스트라 알고리즘을 3번 실행해야 한다. 1에 대하여 실행해 1->B, 1->C의 최단 거리를 알아야 하고 B에 대하여 실행해 B->C, B->N의 최단 거리를 알아야 하고 C에 대하여 실행해 C->B, C->N의 최단 거리를 알아야 한다. N까지 가는 두가지 경로 중 작은 것을 택하면 된다. 다익스트라 알고리즘의 자세한 구현 설명은 myunji.tistory.com/344 [백준] 1753번 : 최단경로 문제 풀이 TMI 난 사실 다익스트라 알고리즘에 트라우마가 있다. 바로 지금보다도 훨씬 아무것도 모르던 2학년 2학기 시절 라이브러리 하나 없..