(JAVA) 백준 15559번 : 내 선물을 받아줘 --- [DFS]

www.acmicpc.net/problem/15559

15559번: 내 선물을 받아줘

 

안녕하세요.

 

DFS 알고리즘 문제입니다.

 

 

크게 어렵지 않고, 헷갈리는 부분만 있습니다.

 

놓을 수 있는 선물 하나 당 하나의 사이클 입니다.

 

 

 

즉, DFS 알고리즘을 통해 사이클 여부를 찾고, 사이클인 경우 선물 갯수를 ++ 하면 됩니다.

 

또한, 탐색 여부를 Level 별로 따로 2차원 배열에 저장하여

 

DFS 탐색 시 한번도 방문하지 않은 곳 인 경우에만 계속 탐색을 진행하고,

 

만약 같은 Level인 곳을 방문한 경우에는 지금 사이클을 이뤘다는 뜻이므로 선물 개수를 추가하면 됩니다.

 

이 때, 유의하실 점은 

 

여기서 무조건 ㅁ - | 만 사이클이 아니라는 것입니다.

 

무슨 말이냐 하면

 

EWWW

SEWN

EEEN

 

과 같은 경우에는, 

 

EWWW

SEWN

EEEN

 

단 두 개의 부분만 사이클 입니다.

(0, 2) 와 (0, 3) 의 W에서 시작했을 때, EW 로 수렴하기 때문에 해당 자리에 선물놔도 결국 다시 주워가지 못하게 됩니다.

 

이러한 경우 때문에 단순히 방문 여부를 boolean 으로 잡게 된다면, 무한 반복이 일어날 수 있어서 int로 Level 별 표시를 해두는 겁니다.

 

 

 

위 사항만 알고간다면 쉽게 해결하실 수 있을 겁니다.

 

 

이상입니다.

 

댓글 감사합니다.

 

감사합니다!

 

 

 

소스코드

---