욱이의 IT 생존일지

문제로 이동하기 https://www.acmicpc.net/problem/17070 여담 오랜만에 DP를 풀어봤습니다. 솔직히 요즘 BFS만 공부하다보니 DP에 소홀해져서 많이 걱정했는데, 스스로 이 문제를 풀게 돼서 정말 기쁘고 행복(?)했습니다! ㅋㅋㅋ 아.. 진짜 예제 입력들 전부 넣어보고 마지막 답이 정확하게 일치하는 거 보고 현실로 탄성을 질렀습니다 ㅋㅋㅋ... 잡설이지만 정말 기뻤답니다 🙂 접근 방식 우선 점화식을 세워봐야 합니다. 다른 어려운 문제들에 비해선 점화식을 세우기 쉬운 편인 것 같았습니다. 처음에는 너무 단순하게 생각해서 D 배열을 이렇게 정의했습니다. D[i][j] = 파이프의 끝자락이 (i, j)에 위치하도록 이동시키는 방법의 수 이렇게 점화식을 세우고 문제를 접근해보니 일단 ..

문제로 이동하기 https://www.acmicpc.net/problem/16947 접근 방식 큰 순서는 다음과 같습니다. 그래프 내의 모든 사이클과 사이클에 속한 정점을 구한다. 사이클에 속한 정점에 연결된 정점들 중 사이클에 속하지 않은 정점을 방문하며 거리를 구한다. 하지만 이 문제에서 핵심은 사이클을 찾고, 사이클에 속한 정점을 구하는 과정입니다. 위 2번은 그저 찾아낸 정점으로부터 DFS 또는 BFS를 수행하면 쉽게 찾을 수 있습니다. 물론 DFS보다는 BFS로 찾는게 더 효율적입니다. 이유는 후에 설명 드리겠습니다. 트리 N개의 정점과 N-1개의 간선으로 이루어진 그래프는 트리입니다. 트리는 사이클이 없으며, 최단 경로를 DFS와 BFS로 구할 수 있습니다. 만약 이 트리에 간선이 하나 더 추..

접근 방식 오랜만에 풀어본 BFS 문제입니다. 일반 숨바꼭질 문제와 똑같습니다만 추가로 이동 방법까지 출력해야 하는 문제입니다. 이동 방법을 구하는 문제라면 이전에도 살펴보았듯이 이전 부모의 이력을 계속 기록해놓았다가 마지막에 역순으로 출력하는 식으로 해결할 수 있습니다. 이 문제에서는 visited 를 확인하는 배열을 따로 두지 않았습니다. 이유는 부모 이력을 기록하는 배열에 이력이 기록된 상태라면 이미 방문한 노드임을 확신할 수 있기 때문입니다. BFS를 수행하는 과정은 쉬운 BFS 문제들과 거의 유사하기 때문에 코드를 보면서 이해하시는 편이 빠를 것이라 생각합니다. 개선 사항 func printRoute(S int) { if P[S] == -1 { fmt.Fprintf(w, "%d ", S) ret..

여담 MST (Minimum Spanning Tree, 최소 신장 트리) 공부 중에 MST 문제로 이 문제가 포함되어 있는 것을 보고 풀게 되었습니다. 접근 방식 처음에는 "어 그냥 노드 개수 - 1 아닌가?" 하고 "에이 설마.." 했습니다. 그러곤 MST를 공부하면서 익힌 Kruskal 알고리즘을 적용해서 풀어보고자 했습니다. 그러나 제출한 코드에 오류가 있는지 WA를 받아서 질문을 검색하다가 N-1이 답이라는 사실을 알게 되었습니다... 용어 정리 일반적인 그래프에서 사이클을 제거한 후에 Tree로 만들면, 이를 Spanning Tree라 합니다. 또한 Tree의 특성 상, 간선(edge)의 수는 정점(vertex)의 수가 N 개 일 때, N-1개가 됩니다. 이러한 상황에서 MST는 Spanning..