백트래킹 파트 - BOJ 14712(넴모넴모 easy) 질문입니다.

[kim-svadoz]

문제 : https://www.acmicpc.net/problem/14712
코드 : https://colorscripter.com/s/d20ftQ7

백트래킹으로 접근해 구현중에 있는데 디테일한 부분을 놓치고 있는 것 같습니다.. 인터넷 소스가 없어서 요청드립니다!!

[kim-svadoz]

빠른 솔루션 감사합니다!!!!!!!!!!!!!!!!!!!!!!

[tony9402]

안녕하세요 !! 해당 문제 C++, Java, Python (Pypy3) 로 풀어 솔루션 코드 올려보았습니다 !
Java 코드 : https://github.com/tony9402/baekjoon/blob/main/solution/backtracking/14712/Main.java
C++ 코드 : https://github.com/tony9402/baekjoon/blob/main/solution/backtracking/14712/main.cpp
Python 코드 : https://github.com/tony9402/baekjoon/blob/main/solution/backtracking/14712/main.py

[tony9402]

dfs(cnt + 1); // 선택 안하고 다음껄 볼 경우
map[y][x] = 1;
dfs(cnt + 1); // 선택 하고 다음껄 볼 경우
map[y][x] = 0;

아마 이 부분 말씀하시는거 같네요. 일단 하나씩 설명드리자면 map 배열은 "넴모"가 있는지 체크를 하는 배열이에요. 0이면 넴모가 없는 경우, 1이면 넴모가 있는 경우.

첫번째 dfs 는 현재 위치에 "넴모"가 없다고 놓고 그 다음 부분을 보는거고, 두번째 dfs는 현재 위치에 "넴모"가 있다고 하고 그 다음을 보는 거에요.
"넴모"의 존재를 체크하는 부분은 map에서 하기 때문에 두번째 dfs 함수 호출 전에 현재 위치에 "넴모"가 있다고 1로 표시하는거에요.

위 코드를 조금 더 풀어서 작성하면 아래와 같아요.

map[y][x] = 0; //현재 위치에 "넴모"가 없는 경우
dfs(cnt + 1);
map[y][x] = 0; 

map[y][x] = 1; //현재 위치에 "넴모"가 있는 경우
dfs(cnt + 1);
map[y][x] = 0;

[tony9402]

"넴모"가 2x2 배열에 다 있지 않도록 가능한 모든 배치를 만들면서 개수를 세는걸로 생각하시면 조금 더 이해하기 쉬울꺼에요

[kim-svadoz]

답변 감사합니다. 후에 말씀해주신 부분에서 조금 더 이해가 되었습니다. 그러니까,
if(map[y - 1][x] == 1 && map[y][x - 1] == 1 && map[y - 1][x - 1] == 1)
이 조건이 만족하고, 현재 위치에 "넴모"를 올려둔다면 문제의 조건에 위배되므로 굳이 "넴모"를 올려두고 이를 모두 지우는 행위를 하지 않고 바로 다음 칸으로 넘어가는 것이 맞나요?

정말 문제는 민상님이 올려주신 cpp 코드나 java코드를 보면서 든 생각은 답을 보면서 이해하면 어렵지 않은데 막상 스스로 문제를 구현하려면 생각이 나질 않습니다.. 앞으로 민상님 문제집으로 더 많은 수련을 해야겠습니다ㅜ

[tony9402]

넹 그 경우는 "넴모"를 놓을 수 없는 곳이니깐 바로 그 다음 칸으로 넘어가요

[kim-svadoz]

친절한 설명 진심으로 감사드립니다