백준 1189: 컴백홈 - javascript(dfs)

문제 출처 

https://www.acmicpc.net/problem/1189

1189번: 컴백홈

문제

한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.

      cdef  ...f  ..ef  ..gh  cdeh  cdej  ...f 
      bT..  .T.e  .Td.  .Tfe  bTfg  bTfi  .Tde 
      a...  abcd  abc.  abcd  a...  a.gh  abc. 
거리 :  6     6     6     8     8    10    6

위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것이다.

입력

첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다.

출력

첫 줄에 거리가 K인 가짓수를 출력한다.

예제 입력 1 복사

3 4 6
....
.T..
....

예제 출력 1 복사

4

문제 풀이 힌트 

- 백트래킹 활용 : 보통 dfs 더 구현 쉬움 

- 백트래킹을 활용해서 경로의 모든 경우의 수를 구하고, 거리가 K인 개수를 구하는 문제임. 

 

문제 풀이 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const [R,C,K] = input.shift().split(' ').map(v => +v); 
const graph = Array.from({length:R}).map(() => []); //주어진 그래프 생성
for(let i=0; i<R; i++){ //그래프에 주어진 map 넣기 
    graph[i] = input[i].split('')
}
const visited = Array.from({length: R}).map(() => new Array(C).fill(false)); //방문 표시
//왼, 오, 아, 위
const dx = [-1,1,0,0]; 
const dy = [0,0, -1,1]; 

let cnt = 0; //개수 세기 
function dfs(y,x, dep){
    if(dep === K){ //거리가 K이면서, 
          if(y === 0 && x === C-1){ //집의 좌표일때, 
            cnt++; 
       }   
        return; 
    }
    for(let i=0; i<4; i++){
        let nx = x + dx[i]; 
        let ny = y + dy[i]; 
        if(nx <0 || ny <0 || nx >=C|| ny >=R || graph[ny][nx] === 'T' )continue; //그래프를 벗어나거나 'T'인건 지나친다.  
        if(!visited[ny][nx]){ //방문하지 않은 좌표일때, 
            visited[ny][nx] = true; //방문한다. 
            dfs(ny, nx, dep+1); //방문하면서 dep를 +1
            visited[ny][nx] = false; //dfs를 빠져나오면서 방문 안함 표시 
        }
    }
}

visited[R-1][0] = true; //현수가 있는 시작 부분은 방문한것임
dfs(R-1,0,1);

console.log(cnt);

Only 문제 풀이 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const [R,C,K] = input.shift().split(' ').map(v => +v); 
const graph = Array.from({length:R}).map(() => []); 
for(let i=0; i<R; i++){
    graph[i] = input[i].split('')
}
const visited = Array.from({length: R}).map(() => new Array(C).fill(false)); 
const dx = [-1,1,0,0]; 
const dy = [0,0, -1,1]; 

let cnt = 0; 
function dfs(y,x, dep){
    if(dep === K){
          if(y === 0 && x === C-1){
            cnt++; 
       }   
        return; 
    }
    for(let i=0; i<4; i++){
        let nx = x+ dx[i]; 
        let ny = y + dy[i]; 
        if(nx <0 || ny <0 || nx >=C|| ny >=R || graph[ny][nx] === 'T' )continue; 
        if(!visited[ny][nx]){
            visited[ny][nx] = true; 
            dfs(ny, nx, dep+1); 
            visited[ny][nx] = false; 
        }
    }
}

visited[R-1][0] = true; 
dfs(R-1,0,1); 

console.log(cnt);