접근 문제를 보고 일반적인 그래프 탐색 문제라고 생각했다. 여기서 어려웠던점은 벽을 한개까지 부술수있다는 점인데 이 부분이 너무 까다롭다고 느껴졌다. 처음 생각은 bfs를 한번 돌리고 그러면서 닿는 벽들의 좌표를 set에 저장하고 벽을 빼고 넣으면서 계속 bfs를 돌리려는 생각을 했다. 또 두번째 생각은 처음과 끝에서 bfs를 돌려서 각각 맞닿는 벽을 set에 저장하고 이 두 set의 교집합을 통해 뺄 벽을 정하는 방법을 생각했다. 하지만 두 방법 모두 시간이 오래걸려 결국 실패했다. 그리고 마지막에 할 수 있었던 생각이 visit을 3차원으로 만드는 것이었다. bfs는 각 visit[i][j][0] 가 있다면 항상 가장 빠르게 도달하는 횟수가 visit[i][j][0]에 저장된다. visit[y][x]..

접근 트리에서 임의의 한점이 선택된다고 생각하자. 그렇다면 거기서부터 어떻게 트리의 최대 거리를 구할 수 있을까? 최대 거리는 가장 먼 2개의 점을 고르는 것과 같다. 임의의 한점에서 가장 먼 노드로 간다면, 가장 먼 2개의 점중 한점에 가게된다. 그리고 그 두개의 점중에서 가장 먼 노드를 구한다면 어떤 점으로 처음 출발하더라도 가장 긴 지름을 구할 수 있다. 가장 먼 노드를 구하는 방법은 bfs, dfs(다익스트라) 모두 가능하다. 전에 1167 트리의 지름으로 이미 풀어본 문제인데 복습할겸 다양한 방법으로 풀어봤다. 요즘 다익스트라가 너무 익숙해져서 힙을 이용한 다익스트라로도 풀었는데 heappop은 시간복잡도가 O(logn)이고 모든 노드가 한번씩 방문되기 때문에 queue를 쓰는것과 계산상 다를게..

접근 1.트리를 어떻게 표현해야할까. 배열 ? 그래프? 예제 입력 케이스를 보니 그래프가 편할거 같아서 선택 2.어떤 정점부터 그래프 탐색을 진행해야 지름을 구할 수 있을까. 리프 노드에서 리프 노드까지일텐데 그래프의 length가 1인 경우를 구하면 되려나? 1번 노드에 2, 3, 4, 5 , 6, 7 번 노드가 연결된 경우를 생각해보자 (1) 1 2 3 4 5 6 (2) (3) (4) (5) (6) (7) 이런 그래프가 있다면 (7) -> (1) -> (6) 을 방문하는 경우가 최대인데 안되겠다. 근데 어떤곳에서 그래프 탐색을 탐색을 하면 가장 먼 노드가 구해지고 그 노드부터 가면 최대값이 구해지겠다. bfs와 dfs로 둘다 풀어보자! 나의 코드1 (dfs) import sys input = sys...

접근 1. 진실을 아는 사람이 파티에 참여하면 거짓을 말하지 못한다. 2. 또다른 파티에서는 과장된 이야기를 들었을 때도 거짓말쟁이로 알려지게 된다. 진실을 아는 사람 그룹을 만들고 진실을 아는 사람이 파티에 있을때 bfs를 이용해 연관되어있는 사람을 모두 진실을 아는 사람 그룹에 넣는다. 그 후 해당 그룹에 인원들이 모두 없는 파티만 세어준다. ex) 5 4 1 1 2 5 2 2 2 3 2 3 1 마지막에 1번이 있지만 1번이 진실을 알아 3번도 진실을 알게되고 2번도 3번이 알아서 진실을 알게되고 결국 5번도 진실을 알게된다. 따라서 마지막 1번이 발견했을때 그래프로 같은 집합에 있는 모든 사람을 진실을 아는 사람 그룹에 넣어야한다. 나의 코드 import sys input = sys.stdin.re..