[백준 1189번 / C++] 컴백홈

dfs를 활용해서 완전 탐색으로 풀면 된다. 

 

1. dfs 기본 문법을 활용해서 상 하 좌 우에 조건에 부합되면 들어간다. 

2. 집의 좌표값과 일치하고 좌표값까지의 distance가 K와 일치하면 cnt+1을 해준다. 

3. 재귀 처리후 돌아오면 visited 배열을 0으로 세팅한다. (다른 방향으로 가는 루트도 체크 해줘야하기 때문에 초기화)

  

    
    
    
    
  
#include <iostream>
using namespace std; 
int dx[4] = { 0,0,-1,1 }; 
int dy[4] = { 1,-1,0,0 }; 
int m, n, k;
int map[5][5]; 
int visited[5][5]; 
int cnt; 
void dfs(int y, int x, int dis) {
	if (x == n - 1 && y == 0&&dis==k) {
		cnt++; 
		return; 
	}
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || nx >= n || ny < 0 || ny >= m )continue; 
		if (visited[ny][nx]|| map[nx][ny])continue;
		visited[ny][nx] = 1; 
		dfs(ny, nx, dis + 1); 
		visited[ny][nx] = 0; 
	}
}
int main() {
	cin >> m >> n >> k; 
	for (int i = 0; i < m; i++) {
		string s; cin >> s; 
		for (int j = 0; j < n; j++) {
			if (s[j] == 'T')map[i][j] = 1; 
		}
	}
	visited[m - 1][0] = 1; 
	dfs(m - 1, 0, 1); 
	cout << cnt; 
}

 

1189번: 컴백홈