나에게는 제법 난이도 있는 문제중 하나이다.

저번에 DFS글이 배열을 다루는 것이였다면

이번 글은 그래프를 다루는 글이 될것 이다.

🔥 기본 경로 탐색

아마 알고리즘을 나와 같이 처음 접하고 문제를 푸는 사람이라면 이런 문제에서 손도 못댈 것 같다..

• 나도 그랬다.

현재는 어느정도 느낌을 잡고 푸는 중이다.

• 완벽하지는 않지만 슬슬 느낌이 오고 있는 듯 싶다.

풀이 코드이다.

우리가 가장 중요시 해야하는 점은 바둑판같은 배열을 만드는 것이 아니라

내가 갔다온 지점은 기억을 해야 한다

이 부분이 가장 중요하다.

저 부분을 하는 역할은 ch배열이다.

자 일단 체크 배열이라고 하는 ch배열 과 바둑판처럼 2차원 배열을 만들었다.

• 이 부분은 누구나 할수 있다고 생각한다.

일단 기본적인 그래프 문제는 모두다 재귀를 통해서 해결을 해야한다.
내가 짠 코드는 모든 경우를 다 돌기 떄문에 비효율적인 재귀라고 할수가 있다.

• 좀있다가 좀더 효율적인 재귀를 다루어 보자.

재귀에 들어가는 값인 idx값은 현재 내 위치를 말한다.

• 즉 index이다.

그뒤 재귀를 돌게 되는데 for문의 최대 값이 N인 이유는 우리가 1에서 트리구조로 펼쳐 보았을떄 다음에 올수 있는 값들은 총 4개이기 떄문이다.

처음에 1의 위치에 있다고 생각을 해보자

그럼 1다음에 갈수 있는 경우의 수는 2,3,4,5가 될것이다.

이것을 for문의 i로 표현한 것이다.

그후 내가 갔다온 지점인지를 확인하는 체크배열,
길이 있는지 = 값이 1인지를 확인한뒤

성공하면 DFS를 돌게 된다.

이떄 중요한 점은 체크 배열을 수정해야 한다는 점이다.

• 다시 0으로 만들어 주는 이유는 해당 위치(노드)를 갔다온뒤 다시 돌아 오는 것을 표현한 것이다.

좀더 효율적인 코드

앞서 보였던 코드는 모든 경우의 수를 다 돌게 된다.

• 즉 값이 1인경우는 싹다 도는 것이다.

이것이 좀더 효율적인 재귀 코드이다.

똑같이 체크 배열은 존재한다.

• 왜냐면 자신의 위치를 표시해야 하기 떄문에

이 board는 바둑판처럼 형성이 되어 있지 않다.

• 단순히 다음 길로 가는 경로만을 표기해 있다.

직접 짜본다면 어떻게 이루어져 있는지는 알수 있을 것이다.

이번에도 for문을 보면 해당 위치에 있는 board의 경로 만큼만 돌게 된다.

예시를 보면

1번에서 갈수 있는 길은 2,3,4이다.

전에는 2,3,4,5 까지 모두 돌면서 경로를 확인했지만

우리는 갈수 있는 길이 2,3,4라는 것을 알고 있기 때문에

2,3,4만큼만 돌면 되는 것이다.

이 코드는 써놓은 것처럼 효율적으로 있는 길만 탐색을 할수가 있으며

따로 board에 길이 있는지를 확인하지 않아도 된다.

• 왜냐면 어차피 길이 있는 값들만 들어가 잇기 때문에

그뒤 DFS를 board에 들어가 있는 길의 값을 넣어주면 통과가 된다.

🔥 미로 찾기

이 문제도 예전에 맛만 봣다가 짠맛을 보고 바로 도망쳤던 문제이다.

바로 코드를 보며 설명을 해보겠다.

일단 우리는 해당 위치에서 위, 오른쪽, 아래, 왼쪽순서로 길이 있는지를 확인할 것이다.

• 그걸 해주는 것이 dx, dy변수 이다.

그후 도착지를 arrive변수로 설정해 준다.

이러한 그래프 문제의 특징은 자기의 위치를 체크해가면서 풀어야 한다는 점이다.

이전 문제도 그렇고 DFS에는 자신의 위치가 들어가게 된다.

• 이 문제는 2차원 배열이 필요하기 떄문에 값이 두개가 들어간다.

그후 이동할 위치를 new변수에 담고 해당 위치가 배열 밖에는 있지 않은지 또 길이 있는지를 확인하면서 for문이 돌게 된다.

그후 길이 있다면 1로 내가 지나간다는 표시를 하고 DFS를 다시 돌리게 된다.

• 마찬가지로 다시 돌아오는 길은 0으로 초기화 해주어야 한다.

이 문제 또한 좀만 생각해서 어떻게 작동을 하는지 알면 굉장히 비효율적이라는 것을 알수가 있다.

• 하지만 미로 찾기라는 알고리즘 문제가 어쩔수가 없다...ㅠ