Baekjoon 3109 빵집 JAVA

https://www.acmicpc.net/problem/3109

3109번: 빵집

https://github.com/JUNGSOONIL/JAVA/tree/main

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 map 데이터가 주어지고, 1열부터 C 열까지 갈 수 있는 최대 개수를 구하는 문제다.

진행은 오른쪽 오른쪽 대각선 위, 대각선 아래 총 3방법으로 갈 수 있고,

이미 도착하면 해당 좌표들은 다시 이용할 수 없다.

​

해당 문제는 DFS로 해결했는데 백트래킹이라는 리턴 부분을 한번 이용해 보았다.

아직 뺵트래킹은 잘 모르겠다 너무 어렵고 헷갈리는 거 같다.

먼저 DFS 델타 값을 이용해 해당 부분들을 방문하고 방문 가능하면 다시 재귀를 해주는데

이때 백트래킹을 이용해서 리턴 값을 줘서 가지치기를 해준다.

그리고 만약 갈수 있으면 그 델타를 더하기 전 좌표에 x를 넣어준다!!

이게 중요한데 x를 넣어주는 이유는

1. 지금 진행 중인 곳이 최종적으로 도착할 경우

2. 지금 진행 중인 곳이 막힐 경우 이 부분을 통하면 어디로 가든 막히기 때문

위의 사항을 유의하여 문제를 풀면 된다.