글 읽기 - 1103번 틀렸습니다....

q8514199 4년 전 1

음 그냥 모르겠습니다.

계속 시간 초과가 나길래 dp와 dfs를 이용해 풀어보았는데

틀렸습니다가 뜨네요...

주석은 열심히 달았습니다... 한번읽어주시고 반례나 이상한 부분 찾아주시면 감사하겠습니다.

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stdlib.h>
#define INF 100
// input이 H로 들어온 경우 INF를 이용하여 처리 
using namespace std;
int N, M, ans, MAX;
int arr[55][55];
//arr 에는 input을 저장
int dp[55][55];
//dp에는 해당 지점(r,c)에서 최대로 이동할 수 있는 수를 저장
int dr[4] = { 0,-1,0,1 }, dc[4] = { 1,0,-1,0 };
//r,c 방향으로 움직일 수 있게끔 배열 설정
bool visit[55][55];
//visit에는 방문했는지 안했는지-> 사이클 체크용 
bool is_ok(int row, int col);
//해당 지점이 범위를 벗어나거나 arr[row][col]값이 H인지 확인
void dfs(int r, int c);

int main() {
	cin >> N >> M;
	for (int i = 0; i < 55; i++) {
		for (int j = 0; j < 55; j++) {
			dp[i][j] = 1;// 맨처음 dp값을 1로 설정
		}
	}
	
	for (int i = 0; i < N; i++) {// input 받기
		string str;
		cin >> str;
		for (int j = 0; j < M; j++) {
			if (str[j] - '0' >= 0 && str[j] - '0' <= 9)// H가 들어온 경우 INF 이용
				arr[i][j] = str[j] - '0';
			else arr[i][j] = INF;
		}
	}
	//제일 좌측 상단부터 탐색 시작
	visit[0][0] = true;
	dfs(0, 0);
	cout << MAX;

}
bool is_ok(int row, int col) {//해당 지점이 범위를 벗어나거나 arr[row][col]값이 H인지 확인
	return  !(row < 0 || row >= N || col < 0 || col >= M || arr[row][col] == INF);
}
void dfs(int r, int c) {
	for (int i = 0; i < 4; i++) {// 해당 지점에서 동서남북 탐색 
		if (MAX < dp[r][c]) MAX = dp[r][c];//dp값의 최대가 정답(MAX) 
		if (is_ok(r + arr[r][c] * dr[i], c + arr[r][c] * dc[i])) {// is_ok 함수를 이용해 해당 지점에 갈 수 있나 판단

			if (visit[r + arr[r][c] * dr[i]][c + arr[r][c] * dc[i]] == true) {
				// visit이 true인 경우: 이미 방문한 부분에 재방문이 가능: 사이클이 있다고 판단하여
				//-1 출력후 강제 종료 
				puts("-1");
				exit(0);

			}
			if (dp[r + arr[r][c] * dr[i]][c + arr[r][c] * dc[i]] != 1) {
				// dp 값이 1이 아닌 경우
				// 해당 지점에서의 최대로 이동할 수 있는 수가 결정되었기에 가지 않는다. 
				continue;
			}
			// 그외의 경우 해당 지점의 visit을 true로 하고 dfs로 탐색한다. 
			visit[r + arr[r][c] * dr[i]][c + arr[r][c] * dc[i]] = true;
			dfs(r + arr[r][c] * dr[i], c + arr[r][c] * dc[i]);

			dp[r][c] = max(dp[r][c], dp[r + arr[r][c] * dr[i]][c + arr[r][c] * dc[i]] + 1);
			// dfs가 끝나면 dp에 해당지점에서 최대로 이동할 수 있는 수를 저장한다
			visit[r + arr[r][c] * dr[i]][c + arr[r][c] * dc[i]] = false;
			// dfs가 끝나면 visit을 false로 바꾼다. 
		
		}
	}
}

q8514199 4년 전 0

헐 감사합니다.. 어디서 문제가 있는지 봐야겠군요...

q8514199 4년 전 0

MAX값을 계산하는 순서를 dp값이 갱신된 후로 바꾸니 해당 문제는 해결되었습니다.. 그래도 틀렸습니다가 뜨네요...

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stdlib.h>
#define INF 100
// input이 H로 들어온 경우 INF를 이용하여 처리 
using namespace std;
int N, M, ans, MAX;
int arr[55][55];
//arr 에는 input을 저장
int dp[55][55];
//dp에는 해당 지점(r,c)에서 최대로 이동할 수 있는 수를 저장
int dr[4] = { 0,-1,0,1 }, dc[4] = { 1,0,-1,0 };
//r,c 방향으로 움직일 수 있게끔 배열 설정
bool visit[55][55];
//visit에는 방문했는지 안했는지-> 사이클 체크용 
bool is_ok(int row, int col);
//해당 지점이 범위를 벗어나거나 arr[row][col]값이 H인지 확인
void dfs(int r, int c);

int main() {
	cin >> N >> M;
	for (int i = 0; i < 55; i++) {
		for (int j = 0; j < 55; j++) {
			dp[i][j] = 1;// 맨처음 dp값을 1로 설정
		}
	}

	for (int i = 0; i < N; i++) {// input 받기
		string str;
		cin >> str;
		for (int j = 0; j < M; j++) {
			if (str[j] - '0' >= 0 && str[j] - '0' <= 9)// H가 들어온 경우 INF 이용
				arr[i][j] = str[j] - '0';
			else arr[i][j] = INF;
		}
	}
	//제일 좌측 상단부터 탐색 시작
	visit[0][0] = true;
	dfs(0, 0);
	cout << MAX;

}
bool is_ok(int row, int col) {//해당 지점이 범위를 벗어나거나 arr[row][col]값이 H인지 확인
	return  !(row < 0 || row >= N || col < 0 || col >= M || arr[row][col] == INF);
}
void dfs(int r, int c) {
	for (int i = 0; i < 4; i++) {// 해당 지점에서 동서남북 탐색 
		if (is_ok(r + arr[r][c] * dr[i], c + arr[r][c] * dc[i])) {// is_ok 함수를 이용해 해당 지점에 갈 수 있나 판단

			if (visit[r + arr[r][c] * dr[i]][c + arr[r][c] * dc[i]] == true) {
				// visit이 true인 경우: 이미 방문한 부분에 재방문이 가능: 사이클이 있다고 판단하여
				//-1 출력후 강제 종료 
				puts("-1");
				exit(0);

			}
			if (dp[r + arr[r][c] * dr[i]][c + arr[r][c] * dc[i]] != 1) {
				// dp 값이 1이 아닌 경우
				// 해당 지점에서의 최대로 이동할 수 있는 수가 결정되었기에 가지 않는다. 
				continue;
			}
			// 그외의 경우 해당 지점의 visit을 true로 하고 dfs로 탐색한다. 
			visit[r + arr[r][c] * dr[i]][c + arr[r][c] * dc[i]] = true;
			dfs(r + arr[r][c] * dr[i], c + arr[r][c] * dc[i]);

			dp[r][c] = max(dp[r][c], dp[r + arr[r][c] * dr[i]][c + arr[r][c] * dc[i]] + 1);
			// dfs가 끝나면 dp에 해당지점에서 최대로 이동할 수 있는 수를 저장한다
			visit[r + arr[r][c] * dr[i]][c + arr[r][c] * dc[i]] = false;
			// dfs가 끝나면 visit을 false로 바꾼다. 
			if (MAX < dp[r][c]) MAX = dp[r][c];//dp값의 최대가 정답(MAX) 
		}
	}
}

q8514199 4년 전 0

바보같은 실수를 하였네여.. 62번째줄에서 핵심적인 문제가 있었습니다. 해당 지점에서 최대로 이동할 수 있는 수가 정해져있으면 MAX값의 후보가 될 수 없는 코드였습니다....

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

문제

문제

출처

ICPC

1103번 틀렸습니다....

q8514199 4년 전 1

q8514199 4년 전 0

q8514199 4년 전 0

q8514199 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말