[알고리즘] Swift -백준 #1189(컴백홈) -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인 가짓수를 출력한다.

 

 

---

분석

한수는 왼쪽 아래점에 있고 집은 오른쪽 위에 있다.

한수가 집에 돌아가는 방법 중 한번 지나치는 곳은 다시 방문하지 않는다.

T로 표시된 곳은 가지 못하는 부분이다.

거리 K가 주어질 때 한수가 집까지 도착하는 경우 중 거리가 K인 가짓수를 구하는 문제

 

풀이 과정

R = 세로, C = 가로, K = 거리

R만큼 반복 .과 T로 구성

 

사이즈가 주어지고 
왼쪽아래 (0,0)에서 오른쪽위(C,R)까지 거리가 K인 가지가 몇 개인가
최소의 거리를 구하는 문제가 아니니까 DFS 를 사용하면 된다.

 

풀이

let input = readLine()!.split(separator: " ").map{ Int($0)!}
let r = input[0]
let c = input[1]
let k = input[2]

var checkArr = Array(repeating: Array(repeating: false, count: c), count: r)
var map = [[String]]()
var distance = Array(repeating: Array(repeating: 0, count: c), count: r)

for _ in 0..<r {
    let input = Array(readLine()!).map {String($0)}
    map.append(input)
}

let dx = [-1, 1, 0, 0]
let dy = [0, 0, -1, 1]

func isValid(y: Int, x: Int) -> Bool {
    return 0 <= y && y < r && 0 <= x && x < c ? true : false
}

var count = 0
func dfs(y: Int, x: Int, d: Int) {
    if y == 0 && x == c-1 && d == k {
        count += 1
        return
    }
    
    for k in 0..<4 {
        let nextY = y + dy[k]
        let nextX = x + dx[k]
        
        if isValid(y: nextY, x: nextX) && !checkArr[nextY][nextX] && map[nextY][nextX] != "T" {
            checkArr[nextY][nextX] = true
            dfs(y: nextY, x: nextX, d: d+1)
            checkArr[nextY][nextX] = false
        }
    }
}


checkArr[r-1][0] = true
dfs(y: r-1, x: 0, d: 1)

print(count)

 

도착지와 거리의 조건을 충족한 경우 카운트를 해주고 더이상 반복하지 않게 끝낸다.

checkArr 에서 true 해준 후 바로 false로 변경하여 다음에도 방문할 수 있게 변경해준다!

 

결과

 

 

 

 

---

📂 정리

길찾기 문제, 경우의 수구하는 문제

출발지에서 도착지까지의 이동경로의 가지 수를 구하는 문제이다.

 

출발지의 좌표와 도착지의 좌표가 헷갈렸다.

처음에는 출발지를 (0, 0)으로 시작했는 데 (0, 0)는 왼쪽 위이다.

문제에서 요구하는 출발지는 왼쪽 아래이기 때문에 (0, r-1) 의 좌표로 시작해야한다.

코드에서 x,y만 바꿔서 입력해주면 된다.