궤도

문제 풀이 일단 다른 섬끼리 다리를 이어야 하기 때문에 각각의 섬을 구분해야 한다. 이런식으로 말이다. myunji.tistory.com/280 [백준] 2667번 : 단지번호붙이기 문제 풀이 문제 이름에 왜 띄어쓰기가 없을까? 그냥 의문점이다. 배열을 돌면서 1로 표시된 지점을 찾으면 그 지점을 root로 하는 bfs 또는 dfs로 연결된 모든 1을 찾는다. bfs, dfs에서 빠져나왔다는 myunji.tistory.com 이 문제에서처럼 dfs를 사용해 각 섬을 구분지을 것이다. 그리고 가장자리에 위치한 모든 땅들에 대해 bfs로 최단거리를 구하는데 만약 이전의 bfs로 구해놓은 최단거리가 4 였다면 거리가 4보다 커질 때 bfs 탐색을 종료해 시간을 아낀다. 소스코드 #include #include..

문제 풀이 이런 그래프가 있다고 하자. 이 그래프를 탐색할 시 선택의 순간이 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..