글 읽기 - dfs에서 빠져나올때 알파벳 방문 표시를 해제하는 위치에 따라 답이 달라지는 이유

junu_ddi 4년 전 0

dfs에서 빠져나올때 알파벳 방문했다는 표시를 해제하는 위치에 따라 답이 달라지는 이유가 궁금합니다.

알아보시기 쉽게 <----------------------이부분 이렇게 주석처리를 했습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
using namespace std;

typedef struct {
	int y;
	int x;
}Dir;

Dir move_Dir[4] = {{-1,0},{1,0},{0,1},{0,-1}};
vector<vector<char> > v(20, vector<char>(20,0));
int arr[26]; //방문한 알파벳을 표시
int r, c;
int maxValue = 0;

bool possible(int y, int x) {
	if (y >= r || x >= c || y < 0 || x < 0) return false; //배열 범위 벗어날때
	if (arr[v[y][x] - 65] == 1) return false; //알파벳이 중복된 경우
	return true;
}

void dfs(int y, int x, int cnt) {
    arr[v[y][x] - 65] = 1; //<-----------------------------------이부분
	int end = 0; //네방향 모두 못가는 경우를 체크하는 변수
 	for (int i = 0; i < 4; i++) {
		int nextY = y + move_Dir[i].y; int nextX = x + move_Dir[i].x;
		if (possible(nextY, nextX)) { //가능하면
			//arr[v[nextY][nextX] - 65] = 1; //<-----------------------이부분
            //'A'=65이므로 index를 위해 65를 뺀다.
			dfs(nextY, nextX, cnt+1);
			//arr[v[nextY][nextX] - 65] = 0; <-------------------------이부분			
		}
		else end += 1; //불가능하면 +1		
		if (end == 4) {//모두 불가능(4)하면 최댓값 갱신 시도
			if (maxValue < cnt) maxValue = cnt;
		}
	}
	cnt--;
	arr[v[y][x] - 65] = 0; //<-------------------------------이부분
}

int main() {
	scanf("%d %d\n", &r, &c);
	for (int i = 0; i < r; i++) {
		char s[21]; cin.getline(s, sizeof(s));
		for (int j = 0; j < c; j++) {
			v[i][j] = s[j];
		}
		cin.clear();
	}
	
	arr[v[0][0] - 65] = 1;
	dfs(0,0,1);
	printf("%d\n", maxValue);

}

djm03178 4년 전 0

둘 다 잘 통과됩니다.

http://boj.kr/5809fceba5c24c6e...

http://boj.kr/c29ad9f226e24045...

djm03178 4년 전 1

질문을 올릴 때는 반드시 틀린 코드를 한 자도 다름없이 올려주시기 바랍니다. 단 한 글자라도 고친 곳이 있다면, 반드시 그 코드를 제출해보고 질문을 올려주세요.

죄송합니다. 제가 이것저것 바꾸고 비주얼 스튜디오에서 수정했다가 붙여넣다가 해서 헷갈렸던 것 같습니다. 다음부턴 명심하도록 하겠습니다. 제가 틀렸던 이유는 알파벳 방문을 초기화하는 위치때문이 아니라 getline으로 입력받을때 char배열을 크기를 20으로 둬서 20 20 의 케이스에서 자리가 모자라 제대로 안 들어가는 문제였습니다. 신경써주셔서 감사합니다! 좋은 하루 되세요!

int main() {
	scanf("%d %d\n", &r, &c);
	for (int i = 0; i < r; i++) {
		//char s[20]; cin.getline(s, sizeof(s)); //<----------------
        char s[21]; cin.getline(s, sizeof(s)); //<------------------
		for (int j = 0; j < c; j++) {
			v[i][j] = s[j];
			//arr[s[j] - 65]++;
		}
		cin.clear();
	}
	/*for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			printf("%c ", v[i][j]);
		}
		printf("\n");
	}*/
	arr[v[0][0] - 65] = 1;
	visit[0][0] = 1;
	dfs(0,0,1);
	printf("%d\n", maxValue);

	
/*	for (int i = 0; i < 26; i++) {
		printf("%d ", arr[i]);
	}*/

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

dfs에서 빠져나올때 알파벳 방문 표시를 해제하는 위치에 따라 답이 달라지는 이유

junu_ddi 4년 전 0

koosaga 4년 전 1

junu_ddi 4년 전 0

djm03178 4년 전 0

djm03178 4년 전 1

junu_ddi 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말