Coding Test 12

[BOJ/13913/Golang] 백준 13913 - 숨바꼭질 4

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

PS/BOJ 2021.06.02

[BOJ/12969/Golang] 백준 12969 - ABC

접근 방식 앞선 포스트에서 소개한 14238번 문제인 '출근 기록' 문제와 유사한 문제입니다. 문제의 조건 하루에 한 명씩 출근한다. 문자열의 길이 = 출근 기록의 길이(N) A는 본인 스스로 짝을 이룰 수 없다. B는 A와 짝을 이룰 수 있다. C는 A, B 모두와 짝을 이룰 수 있다. 반드시 필요한 조건만 정리해보면, 문자열의 길이인 i가 필요합니다. 또한 A가 몇 개 있는지, B가 몇 개 있는지, C가 몇 개 있는지 알아야 합니다. 마지막으로 쌍의 개수를 계속 체크해주어야 하므로, 쌍의 개수도 나타나야 합니다. 그런데 여기에서 변수를 하나 줄일 수 있습니다. 바로 C인데요. C의 개수는 전체 문자열의 길이에서 A의 개수와 B의 개수를 빼준 크기입니다. 따라서, 실질적으로 사용하게 되는..

PS/BOJ 2021.05.24
반응형