0-1 BFS (2) 썸네일형 리스트형 0-1 BFS(0-1 Breadth First Search) 이 게시글에서는 특정한 상황에 놓인 그래프에서 최단 경로를 찾을 때 $O(V + E)$의 시간 복잡도로 해결할 수 있는 0-1 BFS에 대해 다룬다. 거기! 혹시 코테를 준비하신다면? 딱 말할 수 있다. 0-1 BFS를 공부할 것을 강력히 권한다. 본인은 어떤 기업의 코딩 테스트에서 0-1 BFS를 사용할 수 있는 문제를 목격한 뒤로 이 글을 쓰기로 마음먹었기 때문이다. 문제에 비공개 조약이 걸려 있으므로 어떤 기업인지 자세히 말할 수 없지만 전통적인 대기업의 계열사이다. 따라서 대회에 초점을 맞춘 사람이 아니어도 0-1 BFS를 공부해서 손해를 볼 일은 없을 것이다. 0-1 BFS란? BFS는 BFS인데 특수한 환경에서 작동할 수 있는 BFS이다. 그 특수한 환경이 뭐냐고? 0-1을 보면 무엇인지 추측.. 백준 2423 - 전구를 켜라 https://www.acmicpc.net/problem/2423 힌트 더보기 0-1 BFS를 이용하면 가중치가 0과 1로만 이루어진 그래프에서 $O(V + E)$의 시간복잡도로 문제를 해결할 수 있다. 이를 문제에 형태에 맞춰 구현하는 방법을 생각해본다. 만약 문제를 틀린 상태에서 이 게시글을 보고 있는 것이라면 다음 격자로 갈 수 있는 조건을 다시 확인해보도록 하자. 풀이 더보기 문제에 주어진 회로는 최대 8방향으로 탐색할 수 있음을 보여주고 있다. 그리고 회로가 가질 수 있는 위상은 두가지이므로 좌표와 위상을 나타내는 3차원 배열을 생성해서 회로를 돌렸을 때 가중치를 1로 생각해서 0-1 BFS를 수행하면 된다. 다만 회로를 돌린다고 무조건 갈 수 있는 것이 아니다. 다음 두 경우를 보자. 왼쪽의 .. 이전 1 다음
