인프런 커뮤니티 질문&답변

앗 ㅎㅎ 진살라진님 ㅎㅎ 해결하셨군요 ㅎㅎ

담에는 좀 더 빨리 답글 달겠습니다. 요새 프로젝트 때문에 정신이 없어가지구요 ㅠㅠ

저거 근데 누르니까 이케 떠요... 하하.

진살라진님이 답글하신 것도 봤는데요

1. 완전 탐색을 통하여 테스트-케이스 별 결과를 돌려면 반드시 독립적인 사건으로 구분짓기 위해서는 그 영향을 받는 메모리 배열들을 초기화 해야한다.
   *메모리 배열 ex) visited[]

>> 네 맞습니다. 다만 배열들을 초기화하는게 아니라. 해당 노드에서의 정점을 방문 미처리하는 것이기 때문에 원복합니다. 해당 노드의 방문처리를 원복합니다. 가 맞는 워딩같아요.

    visited[y][x] = 0;

이부분이요 :)

1. go() 함수가 리턴되면서 go(ny, nx)에 +1 을 더해줘야
   지나온 노드의 수를 줄 수있다. 다시 말해서, go(ny, nx)를 호출한 함수에 정확히 반영할 수 있다.

>> 네 맞습니다. 해당 노드의 값을 반영할 수 있습니다.

항상 열심히 질문 주셔서 감사합니다.

하루정도 걸려서 스스로 해결해냈습니다..!

수요없는 공급일수도 있겠지만 조회수가 30 정도 있길래,
지나가시다가 공부하실 분들은 참고하시면 좋겠습니다.

코드는 맨 아래에 첨부하였습니다.

1. 완전 탐색을 통하여 테스트-케이스 별 결과를 돌려면 반드시 독립적인 사건으로 구분짓기 위해서는 그 영향을 받는 메모리 배열들을 초기화 해야한다.
   *메모리 배열 ex) visited[]

2. go() 함수가 리턴되면서 go(ny, nx)에 +1 을 더해줘야
   지나온 노드의 수를 줄 수있다. 다시 말해서, go(ny, nx)를 호출한 함수에 정확히 반영할 수 있다.

정리 포인트는 2개로 정리해서 작성해보았습니다.
이해가 가지 않거나, 어려운 부분들의 반박 환영입니다..!

#include<bits/stdc++.h>
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) << "\n";
}