shyram   2년 전

코드가 좀 길어서 코드 설명을 적을게요.

전체적인 진행 과정은 다음과 같습니다.


1. 30줄 이전까지는 각 변수들을 초기화 하는 과정입니다.

2. map의 모든 point에 대해 dfs를 한번 해줍니다. (dfs 함수는 아래에 있습니다)

   # dfs는 서로 다른 섬을 구분하기 위해 사용됩니다.


3. 46줄 부터는 BFS 과정입니다. BFS는 각 섬에서 1칸씩 영역을 넓히며 진행됩니다.

   # 상하좌우를 탐색하는데 같은 섬이 아닌 경우, map이 0인 경우만 탐색합니다.

   # 0인 경우가 있다면 이전 point에 있는 가중치에 1을 더해서 같은 섬으로 만듭니다.

   # 다른 섬을 만났다면 현재 point와 탐색 point의 가중치를 비교합니다.

   # 만약 가중치가 같다면 notoddcount에 최소값이 저장됩니다.

   # 가중치가 다르다면 작은 가중치가 oddcount에 저장됩니다.

   # 다른 섬을 한번이라도 만났다면 go=false 로 인해 더이상 큐에 다음 탐색할 point가 저장되지 않습니다.


4. oddcount와 notoddcount는 처음 다리가 놓인다고 가정하면 2부터 가중치가 주어지므로 1씩 감소시킵니다.


5. 둘 중에 더 작은 값이 출력됩니다.


질문 게시판의 반례를 적용해 보았는데 전부다 맞는 값이 나와서.. 다른 반례가 혹시 있을까요?

djm03178   2년 전

Integer 객체끼리의 비교는 절대로 == 으로 하면 안 됩니다. 반드시 equals() 를 써야 합니다. 두 Integer 객체를 비교하는 것은 두 객체가 완전히 같은 오브젝트인가를 검사하는 것으로, 자바에서 127까지의 Integer 객체는 미리 만들어두고 이를 사용하게 하므로 == 으로 검사가 되지만 그 이상의 수의 경우 새로운 Integer 객체를 매번 만들게 되므로 == 으로 같은 값을 가지는지를 검사할 수 없습니다. 55, 60번째 줄을 각각 equals로 바꾸어주면 답은 맞게 나옵니다.

하지만 이 코드는 다음과 같은 입력에서 시간 초과가 나게 됩니다.


shyram   2년 전

친절한 답변 감사합니다 ㅎㅎ

코드 수정해서 다시 제출해 보도록 하겠습니다!

shyram   2년 전

75번째 줄 if문이 잘못된 위치에 들어갔고, Integer형으로 선언된 배열들을 primitive variable type으로 바꿨더니 accepted 할 수 있었습니다.

지금까지 wrapper class를 사용하고 있었는데 앞으로는 알려주신대로 다른 방법으로 배열을 만들어야 겠습니다.

다시한번 답변 감사드립니다! ㅎㅎ

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