경로가 인접행렬로 주어지고 또, 양방향이라서 그렇습니다.
반복문에서 인접행렬을 입력받고 0부터 순차적으로 부모를 찾아서 초기화하니 어떤 정점이든 초기화 과정에서 최종적으로 나올 가장 낮은 조상이 부모가 됩니다.
1976번 - 여행 가자
경로가 인접행렬로 주어지고 또, 양방향이라서 그렇습니다.
반복문에서 인접행렬을 입력받고 0부터 순차적으로 부모를 찾아서 초기화하니 어떤 정점이든 초기화 과정에서 최종적으로 나올 가장 낮은 조상이 부모가 됩니다.
답변 감사합니다. 저도 말씀하시는거 듣고 이거저거 찾아봤는데요
만약 도시가 5개 주어지고
0 0 0 1 0
0 0 1 0 1
0 1 0 0 0
1 0 0 0 1
0 1 0 1 0
이렇게 간선이 주어지는 상황이라면
처음 parents 배열은
int[] parents = {1, 2, 3, 4, 5} 이런 상황이었다가 반복문을 거치면서
union(1, 4) // parents = {1, 2, 3, 1, 5}
union(2, 3) // parents = {1, 2, 2, 1, 5}
union(2, 5) // parents = {1, 2, 2, 1, 2}
union(3, 2) // parents = {1, 2, 2, 1, 2}
union(4, 1) // parents = {1, 2, 2, 1, 2}
union(4, 5) // parents = {1, 2, 2, 1, 1}
union(5, 2) // parents = {1, 1, 2, 1, 1}
union(5, 4) // parents = {1, 1, 2, 1, 1}
이렇게 변하더라구요
여기서 3번 건물은 find로 찾게되면 2번 건물의 조상인 1을 반환하는데 parents로 찾게되면 2가 반환되니까
parents로 비교했을때랑 find로 비교했을때랑 답이 달라지지 않나요? 좀 헷갈리네요 ㅠㅠ
그러네요 단순 인접행렬이라 그런게 아닌가 생각해봤는데 반례가 있었네요.
말씀하신 반례와 같은 테스트 케이스가 문제 답안에서 주어지지 않아서 생긴 문제 같습니다.
find로 조상을 찾아서 비교하는게 정확한 답안이고, parent로 찾은건 확실하게 오답으로 나와야 하는데 해당 케이스를 고려한 테스트 케이스가 없나보네요...
댓글을 작성하려면 로그인해야 합니다.
hoyho2 8달 전
제출하고나서 깨달았는데 42~44번째 줄에서 parent[]를 비교할게 아니라 find()로 조상을 비교해야 맞는 거더라구요
그런데 정답 처리되길래 이유가 궁금해서 여쭤봐요