cokcjswo   7년 전

1. 컴퓨터가 부숴짐

-> 1번이 아닌 컴퓨터가 부숴질 경우, 모든 컴퓨터는 1번에 연결되어있기때문에 임의의 두 컴퓨터는 1번을 경유해서 연결되어있습니다..

-> 1번 컴퓨터가 부숴질 경우, 다른 모든 노드들이 연결되어있어야합니다 -> '1번을 제외한 MST'가 구성되어야합니다


2. 컴퓨터간 연결이 부숴짐

-> 이 경우는 어떤 연결이 부숴지더라도 '1번을 제외한 MST'가 만들어져있다면 모두 연결 되어있습니다.


어디서 틀렸을 까요 ㅜㅜ


처음에 n == 2일때의 반례를 생각해봤는데 (이 경우 문제자체가 좀 이상해질 수 있을 거같아요, 제가 이해한바로는...)

1 2가 연결 되어있는데, 1과 2 사이의 연결이 끊어지면 1과 2는 다른 컴퓨터를 경유해서 연결되어있어야 하는데 이건 말이 안되죠... 컴퓨터가 2개 밖에 없으니...


제가 뭘 놓치고 있는 걸까요?

cokcjswo   7년 전

해결 했습니다 !!


아이디어는 문제가 없었는데,


제가 유니언파인드 및, 크루스칼을 짜는 버릇중에 하나가 문제있었네요 ㅎ...

yclock   7년 전

궁금증이 해결된 경우에는, 우측 상단의 "해결됨" 버튼을 눌러주세요.

https://www.acmicpc.net/blog/v...


iron1209   4년 전

저도 아이디어가 잘못됬나 생각해서 게시판에 검색해봤는데 마침 있어서 보니까 저랑 같은 경우셨네요 ㅋㅋ

저도 실수해서 틀렸습니다...

댓글을 작성하려면 로그인해야 합니다.