3-L 틀린 부분 피드백 부탁드립니다.

Question

안녕하세요 큰돌님! 강의 잘 보고 있습니다!   3-L 문제를 혼자 해내려고 했다가 문제가 생겨서 이렇게 질문글을 드립니다. https://www.acmicpc.net/submit/1987/56715364   int 형의 dfs함수, go()를 짜보려고 노력했습니다. 그런데 테스트 케이스에 대한 예제 결과는 잘 나오지만, 자꾸 문제 제출 결과는 틀렸다고 나옵니다. 어디서 잘 못 꼬인 것인지 로직 오류 같은데, 제 머리로는 이해가 되지 않아서 이렇게 피드백 부탁드립니다..!   <참고> ret으로 노드마다 방문하였을 때 1씩 쌓이도록 ret+=go(ny, nx)했구요. continue 조건으로 alpha에서 겹치는 노드는 아예 배제하도록 하여서 한방에 찾고 싶었습니다..

kundol · Answer

앗 ㅎㅎ 진살라진님 ㅎㅎ 해결하셨군요 ㅎㅎ 담에는 좀 더 빨리 답글 달겠습니다. 요새 프로젝트 때문에 정신이 없어가지구요 ㅠㅠ 저거 근데 누르니까 이케 떠요... 하하. 진살라진님이 답글하신 것도 봤는데요 완전 탐색을 통하여 테스트-케이스 별 결과를 돌려면 반드시 독립적인 사건으로 구분짓기 위해서는 그 영향을 받는 메모리 배열들을 초기화 해야한다. *메모리 배열 ex) visited[] >> 네 맞습니다. 다만 배열들을 초기화하는게 아니라. 해당 노드에서의 정점을 방문 미처리하는 것이기 때문에 원복합니다. 해당 노드의 방문처리를 원복합니다. 가 맞는 워딩같아요.   visited[y][x] = 0; 이부분이요 :) go() 함수가 리턴되면서 go(ny, nx)에 +1 을 더해줘야 지나온 노드의 수를 줄 수있다. 다시 말해서, go(ny, nx)를 호출한 함수에 정확히 반영할 수 있다. >> 네 맞습니다. 해당 노드의 값을 반영할 수 있습니다.   항상 열심히 질문 주셔서 감사합니다.

qkrwlsxo19547649 · Answer

하루정도 걸려서 스스로 해결해냈습니다..! 수요없는 공급일수도 있겠지만 조회수가 30 정도 있길래, 지나가시다가 공부하실 분들은 참고하시면 좋겠습니다. 코드는 맨 아래에 첨부하였습니다. 완전 탐색을 통하여 테스트-케이스 별 결과를 돌려면 반드시 독립적인 사건으로 구분짓기 위해서는 그 영향을 받는 메모리 배열들을 초기화 해야한다. *메모리 배열 ex) visited[] go() 함수가 리턴되면서 go(ny, nx)에 +1 을 더해줘야 지나온 노드의 수를 줄 수있다. 다시 말해서, go(ny, nx)를 호출한 함수에 정확히 반영할 수 있다. 정리 포인트는 2개로 정리해서 작성해보았습니다. 이해가 가지 않거나, 어려운 부분들의 반박 환영입니다..! #include using namespace std; int dy[] = {-1, 0, 1, 0}; int dx[] = {0, 1, 0, -1}; int R, C, ret, alpha[26], visited[26][26]; char a[26][26]; string s; int go(int y, int x){ visited[y][x] = 1; alpha[a[y][x] - 'A'] = 1; int res = 1; for (int i = 0; i < 4; i++) { int ny = y + dy[i]; int nx = x + dx[i]; if(ny < 0 || ny >= R || nx < 0 || nx >= C || visited[ny][nx] || alpha[a[ny][nx] - 'A']) continue; res = max(res, go(ny, nx) + 1); } visited[y][x] = 0; alpha[a[y][x] - 'A'] = 0; return res; } int main(){ cin >> R >> C; for (int i = 0; i < R; i++) { cin >> s; for (int j = 0; j < C; j++) { a[i][j] = s[j]; } } cout << go(0,0) << " "; }