0-1 BFS (1) 썸네일형 리스트형 [BOJ 26076, 조금 어려움] 곰곰이의 식단 관리 2 (C++) 제일 알고리즘 공부 열심히 하던 시기에 꼭 풀고싶었는데 못풀었던 문제다0-1 bfs에 대해 공부중 관련 문제에 이게 뜨기도 했고무조건 될 거 같은 아이디어가 생각나서 풀었음 일반적인 bfs와 다른 발상이 필요한 문제다 보니 아이디어를 떠올리기 다소 어렵다고 생각한다.https://www.acmicpc.net/problem/26076 가장 기본적인 bfs문제는 1,1 점에서 N,M점까지 이동하기 위해 최소 몇칸을 이동해야 하는지 계산한다.그렇지만 이 문제는 발상을 반대로 해서, 1,1점에서 N,M 점까지 절대 이동하지 못하게 하기 위해최소 몇개의 벽을 놓아야 하는가에 대해 계산하는 문제이다. 간단한 관찰을 거치면 답은 0,1,2중에 무조건 존재함을 알 수 있다.(그래서 애드혹 태그가 붙은듯)그리고 아이디어.. 이전 1 다음
