[Swift][DFS] 백준 16929번 (Two Dots)

요구능력 : DFS응용

 

코드설명 : 

 

문제를 보면 똑같은걸 연속해서 찾는것(?) 이므로 깊이우선탐색으로 풀리는 문제이다.

 

이 문제에서의 핵심

1) 각각의 점이 들어있는 칸이 변을 공유한다.(상하좌우로 이동가능하다.)

2) dk와 d1이 인접해야한다.

d1은 맨 처음에 방문하는 점인데 결국, dk까지 방문해서가면 d1은 이미 방문처리 되어있지만 dk에서 이동가능한 점이라서 맨 마지막에 확인이 가능하다.

 

1. 변수선언 및 입력

좀 복잡하게 입력받은거 같은데 입력받은줄을 for문을 이용해 캐릭터배열로 넣어서 2차원 캐릭터배열로 옮긴것이다.

let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0]
let m = nm[1]
var arr = [[Character]]()
let dx = [0,0,-1,1]
let dy = [1,-1,0,0]
var result = false
var visited = Array(repeating: Array(repeating: false, count: 51), count: 51)
for _ in 0..<n{
    let a = readLine()!
    var char = [Character]()
    for i in a {
        char.append(i)
    }
    arr.append(char)
}

 

2. 이중 for문으로 2차원 배열의 모든점을 한번씩 시작지점으로 둘러본다.

for i in 0..<n{
    for j in 0..<m{
        if !visited[i][j]{
            dfs(i, j, 1, i, j)
        }
    }
}

 

3. dfs로 탐색한다.

시작지점은 방문처리를 해준다.

그리고 4방향으로 갈 수 있는곳인지 없는곳인지 따져서 갈 수있다면 dfs()로 계속해서 탐색해준다.

startX와 startY같은 경우에는 시작지점을 계속해서 저장해주는데 나중에 나올 dk에서 이동가능한점이 시작지점이고 4보다 크거나같을경우 사이클이 완성되기 때문이다.

func dfs(_ x: Int, _ y: Int, _ depth: Int, _ startX: Int, _ startY: Int){
    visited[x][y] = true
    for i in 0..<4{
        let nx = x + dx[i]
        let ny = y + dy[i]
        if nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && arr[nx][ny] == arr[x][y]{
            dfs(nx, ny, depth + 1, startX, startY)
            
        }
        if nx == startX && ny == startY && depth >= 4{
            result = true
            return
        }
    }
    visited[x][y] = false
}

 

후기 : 처음에 보면 어려워보이는데 막상 문제에서 요구하는 사항만 파악하면 잘풀리는문제

let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0]
let m = nm[1]
var arr = [[Character]]()
let dx = [0,0,-1,1]
let dy = [1,-1,0,0]
var result = false
var visited = Array(repeating: Array(repeating: false, count: 51), count: 51)
for _ in 0..<n{
    let a = readLine()!
    var char = [Character]()
    for i in a {
        char.append(i)
    }
    arr.append(char)
}
for i in 0..<n{
    for j in 0..<m{
        if !visited[i][j]{
            dfs(i, j, 1, i, j)
        }
    }
}
if result{
    print("Yes")
}else {
    print("No")
}


func dfs(_ x: Int, _ y: Int, _ depth: Int, _ startX: Int, _ startY: Int){
    visited[x][y] = true
    for i in 0..<4{
        let nx = x + dx[i]
        let ny = y + dy[i]
        if nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && arr[nx][ny] == arr[x][y]{
            dfs(nx, ny, depth + 1, startX, startY)
            
        }
        if nx == startX && ny == startY && depth >= 4{
            result = true
            return
        }
    }
    visited[x][y] = false
}