이전 문제집까진 쉽게 풀었는데 bfs파트부터 꽤 어려웠고 깨달은 점도 많음.


그래서 깨달은 부분을 까먹기도 싫고 공유도 하고 싶어서 작성함.



1. 모든 기반은 결국 '상태 공간'이다.


'벽 부수고 이동하기', '말이 되고픈 원숭이', '숨바꼭질5' 를 풀면서 다시 한 번 확실히 느꼈음.


보통은 상태 공간에 현재 좌표만 넣고 그걸 visit 배열에 체크하는 식인데


위 세 문제는 순서대로 현재 벽을 부쉈는지? 몇번 점프했는지? 짝수 or 홀수 시간에 방문했는지? 의 상태가 더 들어감.


사실 옛날에 '구슬탈출2'를 풀면서도 상태 공간의 중요성을 느끼긴 했는데 위 세 문제로 확실히 깨달음.


'상태 공간의 정의'가 문제의 시작임.



2. 2차원 배열을 탐색하는 문제는 '좌표를 언제 어떻게 넣을 것인가?'가 키포인트다.


'불켜기', '백조의 호수'를 풀고 느꼈음.


'불켜기'는 좀 특별한 bfs였음. 대신 생각할 게 좀 까다로웠던 문제.


암소가 갈 수 있는 지점을 체크해놓고 갈 수 있을 때 그 좌표를 넣어줘야했음.


'백조의 호수'는 '빙산'이랑 비슷한데 구현은 하위호환임.


대신 효율성을 어떻게 가져갈 것인가에 대한 문제임.


이 문젠 'bfs를 제대로 이해하고 있는가?'에 대한 물음인 거 같음.


백조가 만나는지 체크할 때마다 처음부터 다시 진행하고, 못 만나면 visit 배열을 초기화할 필요 없이


못 만나면 더 진행하지 못한 부분의 좌표들을 큐에 담아주면 됐었음.


결국엔 큐에서 하나씩 빼와서 4방향 탐색하는 기본적인 동작에서 어떻게 응용할 것인가? 가 중요한 핵심임.


이 기본 동작을 잘 이해해야 응용이 가능하다.


간단하지만 중요하다 생각함.



이제 dfs로 넘어가야지.