[백준 1261번 / C++] 알고스팟

dfs 문제이다 

 

#접근방법

1. dp (벽을 뚫은 횟수)를 생성한다. (큰 값으로 초기화 ) 
2. dfs 함수를 호출하는데 벽을 만난다면 카운트 +1 을 해주고 아니라면 현재 카운트대로 함수 호출 
3. 만약, dp (벽을 뚫은횟수) 배열에 값이 현재 매개변수로 받아온 카운트 값보다 작다면 갱신해준다. 그게 아니라면 리턴

 

ex)

 

<map> 

 

0 0 1 1

1 1 0 0

 0 1 0 0 

 

 

• 예제1) m[0][0] -> m[0][1] -> map[1][1] -> map[1][2] -> map[2][2] 일때 벽을 총 1번 뚫는다.
• 예제2) m[0][0] -> m[1][0] -> map[1][1] -> map[2][1] -> map[2][2] 일때 벽을 총 3번 뚫는다.  

여기서 보면 현재 위치가 둘다 map[2][2] 이지만 뚫어왔던 벽의 개수가 다르다.

즉, 특정 위치까지 가는 경로중에 벽을 최소로 허물수 있는 경로에서부터 최소값이 만들어지기 때문에 예제2번은 무시하자는 뜻이다.   

즉, 현재 map[2][2]에서부터 최종 도착지까지 벽을 허물어야 하는 최소값은 예제 1번에서부터 도출 되므로, 더이상 예제 2번에서의 경로는 재귀함수를 호출할 필요가 없다.

 

위의 방식을 무시하고 재귀함수를 호출한다면 분명 시간초과가 발생할 것이다.  

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std; 
int map[100][100]; 
int m, n;
int dy[4] = { 0,0,1,-1 }; 
int dx[4] = { 1,-1,0,0 }; 
int visited[100][100]; 
int dp[100][100]; 
void dfs(int y, int x,int cnt) {
	if (dp[y][x] > cnt) {
		dp[y][x] = cnt;
	}
	else return;
	for (int i = 0; i < 4; i++) {		
		int nx = dx[i] + x; 
		int ny = dy[i] + y; 
		if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue; 
		if (visited[ny][nx])continue; 
		visited[ny][nx] = 1; 
		if (map[ny][nx] == 1) {
			dfs(ny, nx, cnt + 1); 
		}
		else {
			dfs(ny, nx, cnt); 
		}				
		visited[ny][nx] = 0; 
	}
}
int main() {
	ios::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0); 
	cin >> n >> m; 
	for (int i = 0; i < m; i++) {
		string s; cin >> s; 
		for (int j = 0; j < n; j++) {
			map[i][j] = s[j]-'0'; 
		}
	}
	memset(dp, 1000000, sizeof(dp)); 
	visited[0][0] = 1; 
    dfs(0, 0, 0);
	cout << dp[m - 1][n - 1]; 
	return 0; 
}

1261번: 알고스팟