[BOJ] 학교탐방하기

[kimdevspace]

문제 링크 https://www.acmicpc.net/problem/13418

풀이 사항 풀이 일자: 2024.00.00 풀이 시간: 00분 00초 채점 결과: 오답/시간 초과/런타임 에러/정답 예상 문제 유형: 구현/BFS/DFS/DP/자료구조/문자열 등 시간: 00 ms 메모리: 00 kb

풀이 방법 (풀이 접근 및 방법에 대한 설명 문제를 풀지 못했다면 어느 곳에서 어려움을 느꼈는지 적어주세요!!)

[kimdevspace]

233

풀이 사항

• 풀이 일자 : 240913
• 풀이 시간 : 35분
• 채점 결과 : 정답
• 예상 문제 유형 : 최소신장트리 프림 크루스칼 그리디
• 시간 : 크루스칼856ms 프림1,024ms
• 메모리 : 크루스칼 131,476kb 프림 191,316kb

  풀이 방법

  크루스칼과 프림 알고리즘에서 그리디적으로 정렬을 어떻게 하냐에 따른 문제이다. 순환 체크를 하면서 가장 비용이 많이 드는 신장트리의 총 비용과, 가장 비용이 적게드는 신장트리의 총 비용을 마이너스 하여 답을 도출함!

[sangholee235]

문제 링크

238

풀이 사항

풀이 일자: 2024.09.17 풀이 시간: 2시간 채점 결과: 정답 예상 문제 유형: 최소 신장 트리 시간: 984 ms 메모리: 159,972 kb

풀이 방법

크루스칼을 몰라서 크루스칼 구현 방식을 학습 한 뒤 적용했습니다.

1. 간선을 목적에 맞는 가중치로 정렬 (최적, 최악)
2. 파인드 연산 (루프에 빠지지 않게?)
3. 유니온 연산 (안 빠지면 경로 병합?)
4. 각 비용 계산 후 차이 계산

[reasonyi]

문제 링크

246

풀이 사항

풀이 일자: 2024.09.18 풀이 시간: 50분 48초 채점 결과: 정답 예상 문제 유형: MST 시간: 1,012 ms 메모리: 161,872 kb

풀이 방법

크루스칼을 이용하여 풀이하였음.

• 처음에 0과 1은 반드시 연결되어있다고 하나, 어차피 입구와 연결된 건물은 1 하나뿐이기에 따로 신경 쓸 필요 없음. -> 이걸 처음에 헷갈려서 삽질함
• 간선은 M+1개가 입력되는 것인데, M개가 입력되는 것으로 착각하여 삽질함
• 오르막길은 1이 아니라 0으로 표현되는데, 이를 착각하여 삽질함

결론: 문제를 잘 읽어야겠다는 다짐을 하게됨.

[kro46]

문제 링크

247

풀이 사항

풀이 일자: 2024.09.18 풀이 시간: 1시간 채점 결과: 정답 예상 문제 유형: MST 시간: 928 ms 메모리: 157,328 kb

풀이 방법

크루스칼을 알고리즘 활용함

1. union-find로 정점 N+1개 parents 배열생성하고, -1로 값 초기화
2. 간선이 M+1개이므로 0~M까지 for문 반복하여 간선정보 입력받음
3. 오르막길은 1이 아니라 0으로 표현되는데, 이를 착각하여 반대로 돌림 -> 근데 테케가 돌아가서 계속 원인을 못찾다가 gpt가 알려줌 ㅋㅋ;; 결론: 문제를 잘 읽어야겠다는 다짐을 하게됨.