🧩 Problem Solving
[BOJ] 백준 13023번: ABCDE
date
Sep 6, 2022
slug
boj-13023
author
status
Public
category
🧩 Problem Solving
tags
BOJ
summary
type
Post
thumbnail
문제링크
문제 분석 및 설계
각 노드에서 DFS 시행했을 때 깊이가 5인 DFS를 찾기만 하면 되는 간단한 문제(라고 생각했었지)
노든 노드(사람)에 대하여 DFS 를 시행하는 것은 너무 비효율적 → 가지치기 요소는 없을까?
⇒ 친구 수 오름차순 정렬 후, 친구가 없는 순서대로 DFS 시행하자(무조건 친구가 적은 쪽에서 먼저 발견함)
Person 객체 생성 및 ArrayList로 저장
- int idx: 나의 번호
- int friends: 나의 친구 수
친구 없는 순서대로 DFS 시행
- 길이 5 도달하면 바로 1 출력 후 main 종료
- 나와 연결된 친구들에 대하여
- 아직 방문 안 했으면 방문처리 및 DFS 재귀호출
- 방문처리 취소
무한 실패.. “그리고 꿈⭐️은 이루어진다”
1차 실패 - 최적화에 눈이 멀었던 섣부른 판단
나의 가정: 친구 수가 가장 적은(연결된 edge 수가 제일 적은) 사람부터 dfs 를 수행해야 가장 길게 dfs 를 들어갈 수 있다
- 친구 수 순서대로 사람을 정렬
- 가장 적은 친구 수를 가진 사람에 대하여 dfs 시행
- 이 과정에서 방문 노드(사람)는 사람 리스트에서 바로바로 삭제하여 dfs 가지치기(중간에 있는 노드에서 또 dfs 를 시작하지 않도록 방지)
- 사람 리스트 확인 → dfs 를 시행했는데 아직 원소가 남아있다는 것은 새로운 그룹이 남아있다는 의미이므로 남은 사람들 중 또 가장 적은 친구 수를 가진 사람에 대하여 dfs 시행
- → 반복
그러나 실패
원인: 위의 가정이 잘못된 것은 아니지만 다른 가정이 추가되어야 함
친구 수가 가장 적은 사람에서 dfs 가 가장 긴 것은 맞지만,
최소의 친구 수를 가진 사람이 여러 명일 경우 그 모든 사람들에 대하여 dfs를 시행하여 비교해야 함!!!
위의 예시의 경우, 노드 1 4 6 이 모두 친구수 1로 최소의 친구를 갖고 있지만
- 1, 4번에서 시작할 경우 최장길이 4
- 6번에서 시작할 경우 최장길이 5
따라서 최소 친구수를 가진 모든 노드에 대하여 dfs 를 시행해봐야 함
1차 실패의 경우, 1번 노드에서 시작하여 최장길이 4를 출력한 후 6번 노드는 이 과정에서 삭제되기 때문에 최장 길이를 찾지 못했음
2차 실패 - 무한 시간초과의 굴레 & 성공 - parameter로 다 넘기기
7%에서 계속 시간초과가 떴다.. 아무리 생각해도 이보다 더 최적화된 방법은 없는 것 같은데ㅜㅜ
visited[], map[][] 등등 static으로 선언해뒀던 변수들을 전부 함수 파라미터로 넘겼더니 겨우 시간초과 탈출
앞으로 dfs 함수 만들 때나 시간복잡도가 클 땐 parameter 로 넘기는 습관을 들여야 할 것 같다.. 너무 괴로웠음