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

답변감사합니다 선생님. 아직 풀리지 않은 의문점이 있는데요..!

선생님답변
그림과 같이 A에서 출발해서 D로 가는 경로중 서로 다른 경로지만 같은 알파벳을 가지고 D에 도착하는 경로를 dp를 이용해줘서 걸러내줘야한다는 질문 게시판 글을 읽었습니다.

-> 제코드는 이 부분이 반영된 코드입니다. A, B, C .. 등의 방문 부분을 visited로 처리해서 해당 알파벳을 방문했다면 재방문이 불가능하게 되어있습니다.

라고 답변해주셨는데요. 저는 가능하다고 생각합니다. 더 자세하게 설명해 주실 수 있나요?

해당 질문을 드릴 때 사용했던사진입니다. A->B->C->D 순서로 1번경로를 따라 다 탐색하고 나서 visited를 0으로 초기화하기 때문에 같은 A->B->C->D 알파벳을 가지긴 하지만 다른 경로인 2번 경로로 탐색할 수 있다고 생각하였고 이러한 탐색이 비효율적이라고 생각하였습니다.

선생님 코드에서는 이 부분이 반영되어있다는 말씀이신거죠?

안녕하세요 ㅎㅎ

선생님의 코드가 통과하는 이유는 테스트 케이스가 부실하다고 생각하면 되는건가요?

-> 아닙니다.

26회 반복문을 돌았기 때문이라고 생각되는데요.

->

제가 수강생님의 26을 추가해서 해봤는데요. 실패가 아니라 시간초과가 납니다. 26이긴 하지만... 이거는 문제에서 주어지는 시간이 짧아서 그럴 가능성이 높습니다.

그리고 for문안의 i를 j로 바꾸셔야 합니다.

수강생님 코드를 + 한 코드입니다. 참고부탁드립니다.

#include <bits/stdc++.h>
using namespace std;
int R, C, ret, ny, nx, visited[30];
char a[21][21];
const int dy[] = {-1, 0, 1, 0};
const int dx[] = { 0, 1, 0, -1}; 
void go(int y, int x, int cnt){
    ret = max(ret, cnt);
    for(int i = 0; i < 4; i++){
        ny = y + dy[i], nx = x + dx[i];
        if(ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
        int next = (int)(a[ny][nx] - 'A'); 
        if(visited[next] == 0){
            visited[next] = 1; 
            go(ny, nx, cnt + 1);
            visited[next] = 0;  
        }else{
            int size = 0;
			for (int j = 0; j < 26; j++) {
				if (visited[j] > 0) size++;
			}
			ret = max(ret, size);
        }
    }
    return;
}
int main(){
    cin >> R >> C;
    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            cin >> a[i][j];
        }
    }
    visited[(int)a[0][0] - 'A'] = 1;
    go(0, 0, 1);
    cout << ret << '\n';
    return 0;
}

그림과 같이 A에서 출발해서 D로 가는 경로중 서로 다른 경로지만 같은 알파벳을 가지고 D에 도착하는 경로를 dp를 이용해줘서 걸러내줘야한다는 질문 게시판 글을 읽었습니다.

-> 제코드는 이 부분이 반영된 코드입니다. A, B, C .. 등의 방문 부분을 visited로 처리해서 해당 알파벳을 방문했다면 재방문이 불가능하게 되어있습니다.

        if(visited[next] == 0){
            visited[next] = 1; 
            go(ny, nx, cnt + 1);
            visited[next] = 0;  
        } 

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

선생님 추가 질문도 있습니다.
3.

그림과 같이 A에서 출발해서 D로 가는 경로중 서로 다른 경로지만 같은 알파벳을 가지고 D에 도착하는 경로를 dp를 이용해줘서 걸러내줘야한다는 질문 게시판 글을 읽었습니다.

해당 코드를 구현하기 위해 이렇게 짜 보았습니다.

하지만 60% 에서 시간초과가 발생하였습니다.

• 선생님은 이 부분을 추가적으로 구현하는거에 대해서 어떻게 생각하시고, 구현하신다면 어떤식으로 구현하실지 궁금합니다.

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

const int max_int = 20;

char a[max_int + 4][max_int + 4];

int dy[] = { 1,0,-1,0 };
int dx[] = { 0,1,0,-1 };

int r, c;
int ret=1;

vector<vector<char>> vvv[max_int+4][max_int+4];
bool flag;

int check[26];


void dfs(int y, int x, vector<char> v, int cnt) {
    ret = max(ret,cnt);

	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		flag = false;
		if (ny < 0 || nx < 0 || ny >= r || nx >= c) continue;

		sort(v.begin(), v.end());
		for (const auto& vv : vvv[ny][nx]) {
			if (vv == v) flag = true;
			if (flag) break;
		}
		if (flag) continue;

		if (check[a[ny][nx] - 'A'])		
			continue;


		vvv[ny][nx].push_back(v);
    
		v.push_back(a[ny][nx]);
		check[a[ny][nx] - 'A'] = 1;
		dfs(ny, nx,v,cnt+1);
		v.pop_back();
		check[a[ny][nx] - 'A'] = 0;
	}
	return;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> a[i][j];
		}
	}

	vector<char> v;
	v.push_back(a[0][0]);
	
	
	check[a[0][0] - 'A'] = 1;

	dfs(0,0,v,1);
	
	cout << ret << "\n";

	return 0;
}

안녕하세요, 인프런 AI 인턴입니다.

질문하신 “3-L 질문입니다.“에 대한 비슷한 관련 질문과 그에 대한 답변을 찾았습니다. 해당 답변은 3-L 코드가 왜 틀렸는지 모르겠습니다. 질문에서 다루고 있습니다.

해당 답변에서는 다음과 같은 중요한 피드백이 포함되어 있습니다:

• DFS 탐색 과정에서의 원복 처리가 비정상적으로 이루어지는 것이 문제였습니다. 올바른 DFS 탐색을 위해서는 방문노드 처리(visited 처리)를 올바르게 관리해야 한다는 점이 강조되었습니다. 방문 처리를 한 노드에 대해 탐색이 종료된 후, 방문 처리를 해제함으로써 다음 탐색에서 재차 해당 노드를 방문할 수 있는 여부를 결정해야 합니다.
  
• 코드 수정을 통해 개선된 접근 방식이 제시되었습니다. 추가적으로 t[a[ny][nx] - 'A']와 같이 문자에서 ‘A’를 빼주는 방식으로 배열 인덱스를 관리하는 방법이 소개되었습니다. 이는 알파벳을 사용하여 배열 인덱스를 지정할 때 유용한 기법입니다.
  

질문자님의 실패 코드와 성공 코드 사이의 차이점을 묻는 부분에 대해, 실패 원인은 말이 몇 칸 지났는지 체크하는 과정에서 발생한 비효율 때문이라고 추측하신 것과 연관이 있을 수 있습니다. 선생님의 코드가 시간 복잡도에도 불구하고 통과하는 것은 체크하는 방법의 효율성에 기인한다고 이해하시면 됩니다. 어떤 경우에는 전체적인 알고리즘의 시간 복잡도는 높아 보여도, 실제로 특정 조건 하에서 파라미터를 관리하고 효율적으로 원복 처리를 하는 방식으로 성능을 크게 향상시킬 수 있습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.