문제 해결 전략
: 연결된 정점들에 대해서 dfs를 수행하면서 번호를 각각 다르게 설정하자.
- 번호를 매긴 뒤 마지막에 연결된 정점이 동일한 번호라고 한다면 false 라는 시퀀스를 작성함.
알아줘야 하는 지식
: 사실 visited 변수는 필요 없다.
- 맨 위에서 colors 값이 -1인지 아닌지를 보고 함수 진입할지 말지 결정하기 때문에 필요 없다.
- visited 사용하는 경우 문제가 되는 코드는
12946. 육각보드
- visited 를 사용하게 되면, 더 이상 아래의 코드로 진입 불가해서 원하는 결과가 나오지 않는다.
- 그리고 기존의 bfs 조건 처리를 이렇게 했는데, 이렇게 하면 안된다.
: 가독성을 위해서 이렇게 반대 조건으로 했는데, 안된다!
- 사실 이렇게 해야 정석이다.
육각보드 결론
- bfs 조건 처리하는 방법을 변경하자.
- 이분 그래프는 visited 없이 작성하자. 오히려 모든 정점에 대해서 순회할 때 visited 때문에 원하지 않는 결과가 나온다.
🔥🔥🔥