[성실코딩 21일차] SWEA #1249 보급로 ***

처음에 보자마자 진짜 쉽다 생각했으나 틀렸음 ㅠㅠㅠㅠㅠㅠㅠㅠㅠ

방법1. DP로 풀었다. 

DP[r][c] = min( 상, 좌 )+map[r][c] 이렇게 풀었는데 틀렸다.

test case 5번까지 맞고 6번부터 틀리다.

아마 r,c를 돌아돌아서 오는 경우를 고려하지않아서겠지?

예를 들면, [4][0]를 오는 방법 중, [0][0]에서부터 우, 하, 하, 하, 하, 좌 이렇게 오는게 더 최소복구시간인데,

지금 풀이법에서는 [0][0]에서부터 하, 하, 하, 하 이렇게 오는 방법만으로 채워주고 있으니까?

방법2. DFS로 풀었다.

DFS로 상하좌우 타고 들어가면서 더 작은값으로 update해줬다.

test case 8번까지 맞고 9번부터 시간초과난다.

방법1 코드

#include < iostream >
#include < string >
#include < algorithm >

#define INF 987654321;

using namespace std;

int n; // 지도의 크기
int map[100][100];
int DP[100][100];

int getMin(int _r, int _c) {
	// 상, 하, 좌, 우
	int up, down, left, right;
	
	// boundary check
	if (_r-1 < 0) {  // 상
		up = INF;
	}
	else {
		up = DP[_r-1][_c];
	}
	if (_r + 1 > n-1 ) {  // 하
		down = INF;
	}
	else {
		down = DP[_r+1][_c];
	}
	if (_c-1 < 0) { // 좌
		left = INF;
	}
	else {
		left = DP[_r][_c-1];
	}
	if (_c+1 > n-1) { // 우
		right = INF;
	}
	else {
		right = DP[_r][_c+1];
	}

	int min1 = min(up, down);
	int min2 = min(left, right);

	if (min1 < min2) {
		cout << "up or down" << endl;
		return min1;
	}
	else {
		cout << "left of right " << endl;
		return min2;
	}
}

void populateDP(int _r, int _c) {
	if (_r==0 && _c==0) { // start point
		DP[_r][_c] = 0;
		return;
	}
	
	else if (_r==(n-1)&&_c== (n - 1)) { // end point
		DP[_r][_c] = getMin(_r, _c);
		return;
	}
	DP[_r][_c] = getMin(_r,_c) + map[_r][_c];
}

int main() {

	int tc;
	cin >> tc;
	for (int i = 1; i <= tc; i++) {
		cin >> n;
		// 입력
		for (int r = 0; r < n; r++) {
			string str;
			cin >> str;
			for (int c = 0; c < n; c++) {
				map[r][c] = str[c]-'0';
				// 초기화
				DP[r][c] = INF;
			}
		}

		// 연산
		for (int r = 0; r < n; r++) {
			for (int c = 0; c < n; c++) {
				populateDP(r, c);
			}
		}

		// 출력
		cout << "#" << i << " " << DP[n-1][n-1] << endl;
	}
	return 0;
}

방법2 코드

#include < iostream >
#include < string >
#include < algorithm >

#define INF 987654321;

using namespace std;

int n; // 지도의 크기
int map[100][100];
int DP[100][100];
int visited[100][100];

int dr[4] = { -1,1,0,0 };  // 상하좌우
int dc[4] = { 0,0,-1,1 };

void dfs(int _r, int _c, int _w) {
	if (_r==(n-1)&&_c==(n-1)) { // 끝, 탈출조건
		return;
	}
	if (_r==0 && _c==0) { // 시작
		visited[_r][_c] = 1;
		DP[_r][_c] = 0;
	}
	
	for (int k = 0; k < 4; k++) {  //상하좌우
		int new_r = _r + dr[k];
		int new_c = _c + dc[k];
		
		// boundary check
		if ( (new_r<0 || new_r>n-1) ||
			(new_c<0 || new_c>n - 1)) { 
			continue;
		}
		// update
		int new_w = _w + map[new_r][new_c];
		if (new_w < DP[new_r][new_c]) {
			DP[new_r][new_c] = new_w;
			if (visited[new_r][new_c]==0) { // 방문한적없을때만 방문
			
				visited[new_r][new_c] = 1; // 방문표시하기
				dfs(new_r, new_c, new_w);
				visited[new_r][new_c] = 0;
			}
		}
	}
	
}

int main() {

	int tc;
	cin >> tc;
	for (int i = 1; i <= tc; i++) {
		cin >> n;
		// 입력
		for (int r = 0; r < n; r++) {
			string str;
			cin >> str;
			for (int c = 0; c < n; c++) {
				map[r][c] = str[c]-'0';
				// 초기화
				DP[r][c] = INF;
				visited[r][c] = 0;
			}
		}

		// 연산
		dfs(0,0,0);

		// 출력
		cout << "#" << i << " " << DP[n-1][n-1] << endl;
	}
	return 0;
}

  아아아 머리아파ㅠ

내일 아래 링크보면서 공부해야겠다.

http://his130.tistory.com/353