(JAVA) 백준 3109번 : 빵집 --- [그리디, 백트래킹, DP]

www.acmicpc.net/problem/3109

3109번: 빵집

 

안녕하세요.

 

이 문제는 그리디가 핵심이고, 백트래킹 방식을 활용했습니다.

 

추가로, 시간초과를 방지하기 위해 DP를 곁들였습니다.

 

 

처음부터 끝까지 연결할 수 있는 파이프의 최대 개수 를 구하는 문제입니다.

 

대신, 한 칸에 하나의 파이프만 설치할 수 있습니다.

 

 

이는 곧, 파이프 위치를 맵에 추가하며 파이프를 설치해야 한다는 것이죠.

 

 

처음에는 가중치가 없기 때문에 BFS와 Boolean 배열을 사용해서 풀 수 있지 않을까? 했지만

 

BFS를 사용할 수 없는 이유는

 

처음 지점부터 끝 지점까지 연결한 파이프는 한 줄이기 때문입니다.

 

즉, 현재 지점에서 오른쪽 위, 오른쪽, 오른쪽 아래 세 지점을 탐색해야 하는데

만약 오른쪽 위 지점을 연결해서 쭉 이어가다 파이프를 연결했다!

 

그럼 다시 돌아와서는 오른쪽과 오른쪽 아래 지점을 탐색할 수 없고

모든 파이프 지점에서 추가 탐색을 그만두게 해야합니다.

 

 

여기까지 생각이 닿으니 BFS 대신에 백트래킹을 사용해야겠다 생각했습니다.

 

그러다 갑자기 하나 든 생각이

 

가장 개수를 많게 하려면 무조건 오른쪽 위에서 아래로 내려오는 우선순위로 파이프를 설치해야 하지 않을까?

 

 

 

여기까진 좋았지만, 시간 초과가 발생했습니다.

 

그 이유는!!

 

보통 백트래킹을 사용하면

 

visited[y][x] = true;

함수실행---------

visited[y][x] = false;

 

로 모든 경우를 돌아보려 합니다.

 

 

하지만 이 문제같은 경우에는

 

이 지점에서 다음에 연결할 파이프 자리가 없으면 마찬가지로 다른 파이프가 해당 지점에 와도 갈 곳이 없다는 것 이죠.

 

그렇기 때문에, 한 번 이 지점에 파이프를 놔두면 바로 맵에 x로 표시해주고

파이프라인을 만들 수 없다! 해도 다시 맵의 x값을 수정하지 않고 그대로 둡니다.

 

이를 통해 시간을 더욱 단축시킬 수 있고, 문제를 통과할 수 있습니다.

 

 

헥헥.. 위에 적은 내용들이 곧 이 문제해결 매커니즘과 일맥상통합니다.

그렇기 때문에 소스코드만 첨부하겠습니다.

 

 

감사합니다.

 

 

소스코드

---