Integer 객체끼리의 비교는 절대로 == 으로 하면 안 됩니다. 반드시 equals() 를 써야 합니다. 두 Integer 객체를 비교하는 것은 두 객체가 완전히 같은 오브젝트인가를 검사하는 것으로, 자바에서 127까지의 Integer 객체는 미리 만들어두고 이를 사용하게 하므로 == 으로 검사가 되지만 그 이상의 수의 경우 새로운 Integer 객체를 매번 만들게 되므로 == 으로 같은 값을 가지는지를 검사할 수 없습니다. 55, 60번째 줄을 각각 equals로 바꾸어주면 답은 맞게 나옵니다.
하지만 이 코드는 다음과 같은 입력에서 시간 초과가 나게 됩니다.
shyram 5년 전
코드가 좀 길어서 코드 설명을 적을게요.
전체적인 진행 과정은 다음과 같습니다.
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. 둘 중에 더 작은 값이 출력됩니다.
질문 게시판의 반례를 적용해 보았는데 전부다 맞는 값이 나와서.. 다른 반례가 혹시 있을까요?