2406번 - 안정적인 네트워크
1. 컴퓨터가 부숴짐
-> 1번이 아닌 컴퓨터가 부숴질 경우, 모든 컴퓨터는 1번에 연결되어있기때문에 임의의 두 컴퓨터는 1번을 경유해서 연결되어있습니다..
-> 1번 컴퓨터가 부숴질 경우, 다른 모든 노드들이 연결되어있어야합니다 -> '1번을 제외한 MST'가 구성되어야합니다
2. 컴퓨터간 연결이 부숴짐
-> 이 경우는 어떤 연결이 부숴지더라도 '1번을 제외한 MST'가 만들어져있다면 모두 연결 되어있습니다.
어디서 틀렸을 까요 ㅜㅜ
처음에 n == 2일때의 반례를 생각해봤는데 (이 경우 문제자체가 좀 이상해질 수 있을 거같아요, 제가 이해한바로는...)
1 2가 연결 되어있는데, 1과 2 사이의 연결이 끊어지면 1과 2는 다른 컴퓨터를 경유해서 연결되어있어야 하는데 이건 말이 안되죠... 컴퓨터가 2개 밖에 없으니...
제가 뭘 놓치고 있는 걸까요?
해결 했습니다 !!
아이디어는 문제가 없었는데,
제가 유니언파인드 및, 크루스칼을 짜는 버릇중에 하나가 문제있었네요 ㅎ...
궁금증이 해결된 경우에는, 우측 상단의 "해결됨" 버튼을 눌러주세요.
https://www.acmicpc.net/blog/v...
저도 아이디어가 잘못됬나 생각해서 게시판에 검색해봤는데 마침 있어서 보니까 저랑 같은 경우셨네요 ㅋㅋ
저도 실수해서 틀렸습니다...
댓글을 작성하려면 로그인해야 합니다.
cokcjswo 6년 전 2
1. 컴퓨터가 부숴짐
-> 1번이 아닌 컴퓨터가 부숴질 경우, 모든 컴퓨터는 1번에 연결되어있기때문에 임의의 두 컴퓨터는 1번을 경유해서 연결되어있습니다..
-> 1번 컴퓨터가 부숴질 경우, 다른 모든 노드들이 연결되어있어야합니다 -> '1번을 제외한 MST'가 구성되어야합니다
2. 컴퓨터간 연결이 부숴짐
-> 이 경우는 어떤 연결이 부숴지더라도 '1번을 제외한 MST'가 만들어져있다면 모두 연결 되어있습니다.
어디서 틀렸을 까요 ㅜㅜ
처음에 n == 2일때의 반례를 생각해봤는데 (이 경우 문제자체가 좀 이상해질 수 있을 거같아요, 제가 이해한바로는...)
1 2가 연결 되어있는데, 1과 2 사이의 연결이 끊어지면 1과 2는 다른 컴퓨터를 경유해서 연결되어있어야 하는데 이건 말이 안되죠... 컴퓨터가 2개 밖에 없으니...
제가 뭘 놓치고 있는 걸까요?