[DFS] 백준 실버1 11403번: 경로 찾기(Swift)

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

11403번: 경로 찾기

풀이과정

해당 문제는 주어진 행렬을 통해 좌표의 경로를 찾는 문제이다.

먼저, 예제를 풀이하자면

위 예제를 통해

(0, 3), (1, 6), (3, 4), (3, 5), (4, 0), (5, 6), (6, 2)의 좌표가 1인 것을 알 수 있다.

이를 보기좋게 정점으로 나눠 표현하면,

0  0 -> 3 -> 4 -> 0 / 0 -> 3 -> 5 -> 6 -> 2

1 1 -> 6 -> 2

2 X

3 3 -> 4 -> 0 / 3 -> 4 -> 6 -> 2

4 4 -> 0 -> 3 -> 4 / 4 -> 0 -> 3 -> 5 -> 6 -> 2

5 5 -> 6 -> 2

6 6 -> 2

위와 같이 풀 수 있다.

이를 코드를 통해 행렬을 만들기 위해서는 DFS를 활용하여 하나씩 경로를 탐색을 통해 탐색한 위치에 1을 저장해야한다.

let N = Int(readLine()!)!

var link: [[Int]] = Array(repeating: [], count: N)
var result = Array(repeating: Array(repeating: "0", count: N), count: N)

for i in 0..<N {
  let y = readLine()!.split(separator: " ").map { Int($0)! }
  for j in 0..<y.count {
    if y[j] == 1 {
      link[i].append(j)
    }
  }
}

func dfs(i: Int, line: Int) {
  for j in link[i] {
    if result[line][j] != "1" {
      result[line][j] = "1"
      if i != line { dfs(i: i, line: line) }
    }
  }
}

for i in 0..<N {
  dfs(i: i, line: i)
}

for line in result {
    print(line.joined(separator: " "))
}

코드를 설명하자면,

먼저, link라는 배열을 통해 정점 i가 갈 수 있는 j을 배열에 담아주었다.

그다음으로 dfs 메서드를 구현하였다.

dfs 메서드 내부는 link[i]라는 배열을 통해 i에서 갈 수 있는 j을 가져와 result의 해당 좌표에 1을 저장한다.

이때 이미 1이 저장되어 있으면 더 이상 탐색할 필요가 없기 때문에 다음 j을 탐색하고,

추가로, i와 현재 line이 같으면, 사실상 탐색이 끝난 것이기 때문에 패스한다.

이처럼 dfs을 라인별로 반복문을 통해 호출해 주면 문제를 해결할 수 있다.