bckim7065   3년 전

[소스코드]

- 아래첨부

[질문]

메인 메소드 61번째 줄 node[b][a] = 1; 부분이 잘 이해가 가지않습니다.

연결관계를 등록하기 위해서 node[a][b] = 1; 이부분만 해주면 알수있을것같은데 node[b][a] = 1; 부분도 등록 해주는 이유를 모르겠네요 

BFS 개념이 익숙하지 않아서 다른사람 코드를 보더라도 이해가 쉽지않네요 찾아볼수있는 부분이나 힌트라도 주시면 찾아보겠습니다.

shg9411   3년 전

a와 b가 연결되어있다고 치면, 어느 컴퓨터가 바이러스에 걸리던 둘 다 바이러스에 걸리는게 맞겠죠.

단순히 node[a][b]=1만 해준다면 a가 바이러스에 걸렸을 때 b도 걸리는 것은 확인할 수 있지만

b가 바이러스에 걸렸을 때 a가 걸리는 것을 확인할 수 없습니다.

방향이 없는 그래프에서 간선은 양쪽 정점에 추가해줘야합니다.

추가로 소스는 글 작성하실 때 소스 추가로 추가해주시면 다른 분들이 조금 더 편하게 코드를 확인할 수 있습니다.

bckim7065   3년 전

shg9411 님 댓글 감사합니다. 보고 바로 수정했습니다^^


질문에 조금을 추가하자면 해당 문제를 풀떄 61번째 라인 node[b][a] = 1; 부분을 빼버리고 제출을하게되면 문제가 틀렸다고 나오더라구요

제가 생각했던 부분은 node[a][b]=1 부분만있다면 인접한 노드들을 순차적으로 접근하면서 해당문제에서는 문제가 없을것같았는데 제출했을시 오답으로 나오는겄을봤을 떄 

해당로직에 대한 반례가있는것같은데 위의부분이랑 관련된것일까요?

shg9411   3년 전

설명은 위에 써드린 것 같고,

반례입니다.

bckim7065   3년 전

아.. 이해했습니다 감사합니다!!! 

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