백준 13565 침투, DFS 깊이우선탐색 swift언어 문제풀이

 

 

 

최근에 알고리즘 문제를 너무 안풀어서 오랜만에 실버문제 하나를 풀고 포스팅을 해봅니다.
백준 13565번 문제, 침투를 풀어보겠습니다.

 

---

백준 13565, 침투 문제 설명

M x N 크기의 격자가 있을때, 1행의 흰색 영역에서 시작해서 맨 마지막 행의 흰색 영역에 도달할 수 있는지를 체크하면 되는 단순한 그래프 유형 문제입니다. 격자에 "1"이 표시되면 검은영역, "0"이 표시되면 흰영역(침투 가능한 영역)을 의미합니다. 그럼 바로 swift 언어로 문제를 풀어보겠습니다.

 

 

 

---

백준 13565, 침투 문제 swift 풀이

상, 하, 좌, 우 좌표를 정의한 dx, dy 상수배열을 먼저 선언했습니다. 이후  R, C(행, 열) 상수를 입력받았습니다. G는 격자 정보를 담을 이차원 배열입니다. visit은 현재 격자의 방문여부를 판단할 이차원 배열입니다.

 

 

 

 

격자의 1행 위치를 돌면서, 흰 영역일 경우, 위의 DFS 메서드를 돌릴겁니다. 4방향에 대하여, 격자 밖을 벗어나는지, 검은 영역인지, 이미 방문한 영역인지 체크하고, 방문하지 않았다면 DFS로 탐색을 시작합니다.

 만약 탐색하는 곳이 R-1, 행의 끝에 도달하는 경우, true를 반환합니다. 행의 끝에 도달할 수 있는 경우의 수가 1가지라도 존재한다면, 침투가 가능함을 의미하기 때문입니다.

 

 

 

 

0번째 행(배열은 zero based index이므로, 첫번째 행이 0으로 시작)의 격자를 탐색합니다. 만약 아직 방문하지 않았고 + 흰 영역, "0"인 경우에는 방문체크를 하고(29행) 해당 0행 idx열부터 시작하여 맨 마지막 행 위치까지 침투 가능한지 체크를 하기 위해 DFS를 돌립니다.

 이렇게 모든 경우의 수를 돌리면서 DFS 메서드가 true를 반환하는 경우가 한번이라도 있다면 ans는 true값을 갖게 됩니다. 마지막 33행에서는 침투 가능여부를 담고 있는 ans 변수를 출력하고 있습니다.

 

 

---

지금까지 기본 그래프문제인 백준 13565, 침투문제를 풀어봤습니다. 질문이나 의견 댓글 환영합니다. 전체소스코드 아래 첨부드리겠습니다. 즐거운 하루되세요.

let dx = [0, 0, -1, 1]
let dy = [-1, 1, 0, 0]
let ip = readLine()!.split(separator: " ").map { Int(String($0))! }
let (R, C) = (ip[0], ip[1])
var G = [[Character]]()
var visit = [[Bool]](repeating: [Bool](repeating: false, count: C), count: R)

(0..<R).forEach { _ in
    G.append(Array(readLine()!))
}

func DFS(_ x: Int, _ y: Int) -> Bool {
    for idx in dx.indices {
        let nx = x + dx[idx]
        let ny = y + dy[idx]
        if nx < 0 || ny < 0 || nx >= R || ny >= C { continue }
        if visit[nx][ny] || G[nx][ny] == "1" { continue }
        visit[nx][ny] = true
        if nx == R-1 { return true }
        if DFS(nx, ny) { return true }
    }
    return false
}

var ans = false

for idx in G[0].indices {
    if G[0][idx] == "1" || visit[0][idx] { continue }
    visit[0][idx] = true
    if DFS(0, idx) { ans = true; break }
}

print(ans ? "YES" : "NO")