https://www.acmicpc.net/problem/1941 << 문제 링크


http://boj.kr/18ade393c1f14a3ca2c120bfc49e9030 << 내 소스 링크


처음에 '십자 모양 어떻게 탐색하지?' 고민할 때


bfs인가? 했는데 bfs는 호수에 돌 던질 때 생기는 파동 마냥 퍼져 나가니까 이것도 아닌데... 하다가


최근에 C 공부할 때 '2차원 배열은 1차원 배열을 길게 늘린 거에 불과하다' 라면서 


ram에 어떻게 저장 공간이 생기고 참조되는지 본 기억이 번뜩 떠오른거임!!


바로 노트에 예제로 나온 2차원 배열을 1차원으로 이어붙여 만들어보니까 십자모양도 탐색 쌉 가능각이 보임.


그냥 25개 중에 7개 다 뽑아보면 되겠구나, 시간 복잡도도 40만 정도네, 생각하고 구현에 들어감.


처음에는 뽑을 때마다 인접한 여학생이 있는지 체크하면서 뽑아서 제출하니까 틀림.


'어 야발 뭐지? 이거 아닌가?' 하다가 내가 막 반례 만들어보려고 넣어보니까 왜 안되는지 알겠더라.


뽑을 때마다 주위 체크하면서 뽑으면 나중에 만들어지는 정답을 못 만듦; 이건 글로 잘 전달을 못하겠네.


그래서 일단 다 뽑아재낀 다음에 기저사례에서 다시 dfs 돌려서 


인접한 애들이 7명이면 성공이니까 1 리턴하는식으로 고치니까 정답됨.


와 개짜릿하네 ㄷㄷ