아.. 진짜... 역대급으로 힘든 문제였다..
어제.. 두번째 문제로 선택했다가 오늘 오후 4시에 해결한 상황 ^^ 물론 그 중에 한 10시간 정도는 현실 도피였음ㅋㅋㅋㅋㅋ
암튼, 어제부터,, 오늘까지 해결한 문제는 BOJ 16432 떡장수와 호랑이 이다.
BOJ 16432 떡장수와 호랑이
떡장수 동희는 매일 새벽에 갓 만든 떡을 들고 산을 넘어 장터로 가서 떡을 팝니다. 동희가 만드는 떡의 종류는 1번부터 9번까지 있습니다.
산에는 동희가 나타나기를 기다렸다가 동희를 협박하여 떡을 하나 가져가는 호랑이가 살고 있습니다. 이 호랑이는 입맛이 까다로워 전날에 먹었던 떡과 같은 종류의 떡이면 먹지 않습니다. 만약 줄 수 있는 떡이 없다면 동희는 호랑이에게 잡아먹히고 맙니다.
동희는 N일 동안 떡을 팔러 매일 장터에 나가야 합니다. 동희가 만드는 떡들의 종류는 재료 공급 사정에 따라 종류가 매일 달라집니다.
동희가 N일 동안 호랑이에게 잡아먹히지 않도록 호랑이에게 줄 떡들을 골라주세요.
입출력
나의 풀이
가 아니다. 이건 나의 풀이가 아니다,, 짜증 ㅜㅡㅜㅡㅜㅡㅜ 속상,,
처음엔 두가지 접근 방법을 생각했다.
그저 모든 경우의 수를 생각하는 단순한 방식과, 무언가,, 시간을 줄일 수 있는 방법이있겠지 예상했다.
확인차 단순한 방법으로 코드를 짜서 돌려봤지만 예상한대로 시간 초과가 떴다.
중복되는 경우나, 탐색하지 않아도 되는 경우를 미리 판단해 시간을 줄여주는 방법이 필요한 문제였다.
하지만 나는 결국 내 힘으로 이부분을 생각해내지 못했다 ㅜ
방문 체크를 위해 3차원 배열을 사용해야 하나 싶었지만,, 결국 다른 분의 포스팅을 보고 해결했다.
방문 여부를 체크하는 2차원 배열 visited 가 의미하는 바는 다음과 같다.
visited[i][j] = i-1 번째 날에 j 번 떡을 먹고 간 경우를 확인 했는가!
해당 날이 아닌 그 전날에 먹은 떡을 기록하는 거라 너무 헷갈렸다!
배열 visited 이 의미하는 바를 잘 기억하고 재귀적으로 DFS 탐색을 진행한다.
day 에 가져가는 떡 중 하나를 고르고 (riceCake[day][i]), 해당 떡을 고르고 day+1 날로 진행한 경우를 아직 탐색하지 않았다면 최종 정답 배열 answer 의 answer[day] 에 떡을 저장한 뒤 함수를 재귀 호출한다.
재귀적으로 호출한 함수의 결과가 true 이면 가능한 방법이 존재한다는 뜻이므로 함수를 종료하고, 그렇지 않다면 i+1 번째 떡에 대해서 다시 확인하여 방법을 찾는다.
최종적으로 탐색의 결과에 따라 answer 배열을 출력하고 탐색 결과 가능한 방법이 없다면 -1 을 출력하여 마무리 한다.
코드
#include <iostream>
#include <vector>
using namespace std;
int N;
bool visited[1001][10] = {false};
vector<vector<int>> riceCake;
vector<int> answer;
bool dfs(int before, int day){
if (day == N){ // 마지막 날에 먹을 떡 고르기!
for (int i = 0; i < riceCake[day-1].size(); ++i) {
if (before != riceCake[day-1][i]){
answer[day-1] = riceCake[day-1][i];
return true;
}
}
}
for (int i = 0; i < riceCake[day-1].size(); ++i) {
int next = riceCake[day-1][i]; // 먹을 떡
if (before != next && !visited[day+1][next]){ // 이 떡을 먹은 경우를 아직 확인하지 않았다면
visited[day+1][next] = true;
answer[day-1] = next;
if(dfs(next, day+1)){
return true;
}
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>N;
answer.assign(N, 0);
int count;
for (int i = 0; i < N; ++i) {
cin>>count;
int num;
vector<int> cakes;
for (int j = 0; j < count; ++j) {
cin>>num;
cakes.push_back(num);
}
riceCake.push_back(cakes);
}
if (dfs(0, 1)){
for (int i = 0; i < N; ++i) {
cout<<answer[i]<<'\n';
}
}else{
cout<<-1;
}
return 0;
}언제나 풀고나면 쉬워보이는,, ㅜㅡㅜ DFS 탐색을 더 연습해야 겠다,,
할 수 있었을 것 같은데 왜 못한거지,, 너무 속상하다
reference
