1189. 컴백홈

우선 이 문제는 뜻깊은 문제이다. 백준에서 문제를 푼 개수가 600개가 되었다. 이문제는 그 600번째이다.

600개를 풀면서 드는 생각들은 회고로 적어 놓아야 겠다.

이문제는 dfs를 떠올릴 수 있는 구조이다. k의 거리로 이동한 것을 찾으니까 리턴조건은 당연히 거리가 k인것 + '그 위치에 도착했는가' 이다.

 

자스 풀이

const input = require("fs")
  .readFileSync("./dev/stdin")
  .toString()
  .trim()
  .split("\n")
const [r, c, k] = input[0].split(" ")
const dy = [-1, 0, 1, 0],
  dx = [0, 1, 0, -1]
const visited = Array.from({ length: r }, () =>
  Array.from({ length: c }, () => false)
)
const board = input.slice(1)
let ans = 0

function dfs(y, x, cnt) {
  if (cnt == k && y == 0 && x == c - 1) {
    ans += 1
    return
  }

  for (let i = 0; i < 4; i++) {
    let ny = y + dy[i],
      nx = x + dx[i]
    if (
      0 <= ny &&
      ny < r &&
      0 <= nx &&
      nx < c &&
      !visited[ny][nx] &&
      board[ny][nx] != "T"
    ) {
      visited[ny][nx] = true
      dfs(ny, nx, cnt + 1)
      visited[ny][nx] = false
    }
  }
}
visited[r - 1][0] = true
dfs(r - 1, 0, 1)
console.log(ans)

 

 

파이썬 풀이

import sys
sys.setrecursionlimit(10**9)
input =sys.stdin.readline
r,c,k = map(int,input().split())
board = [input().rstrip() for _ in range(r)]
visited = [[0] * c for _ in range(r)]
ans = 0

def dfs(y, x ,cnt) :
  global ans

  if y == 0 and x == c - 1 and cnt == k : 
    ans += 1
    return 

  for dy, dx in (1,0),(-1,0),(0,-1),(0,1) :
    ny , nx = dy + y , dx + x
    if 0 <= ny < r and 0 <= nx < c and board[ny][nx] != 'T' and visited[ny][nx] == 0:
      visited[ny][nx] = 1
      dfs(ny, nx, cnt + 1)
      visited[ny][nx] = 0

visited[r-1][0] = 1
dfs(r-1, 0, 1)

print(ans)