백준 16929 Two Dots Kotlin (dfs) 2022-06-23 코드 추가

문제 출처 : https://www.acmicpc.net/problem/16929

16929번: Two Dots

 

문제

Two Dots는 Playdots, Inc.에서 만든 게임이다. 게임의 기초 단계는 크기가 N×M인 게임판 위에서 진행된다.

각각의 칸은 색이 칠해진 공이 하나씩 있다. 이 게임의 핵심은 같은 색으로 이루어진 사이클을 찾는 것이다.

다음은 위의 게임판에서 만들 수 있는 사이클의 예시이다.

점 k개 d1, d2, ..., dk로 이루어진 사이클의 정의는 아래와 같다.

• 모든 k개의 점은 서로 다르다. 
• k는 4보다 크거나 같다.
• 모든 점의 색은 같다.
• 모든 1 ≤ i ≤ k-1에 대해서, di와 di+1은 인접하다. 또, dk와 d1도 인접해야 한다. 두 점이 인접하다는 것은 각각의 점이 들어있는 칸이 변을 공유한다는 의미이다.

게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구해보자.

입력

첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문자 한 글자이다.

출력

사이클이 존재하는 경우에는 "Yes", 없는 경우에는 "No"를 출력한다.

제한

• 2 ≤ N, M ≤ 50

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색

풀이

dfs문제이다.

우리는 사이클을 찾아야 한다.

문제에서 사이클에 대한 조건은, 같은 색의 점으로 이루어져야 하고(같은 알파벳) 최소 4개의 점으로 이루어져야 한다.

이를 dfs로 판별할 수 있는데, 다음 정점을 탐색하는 조건은 아직 방문하지 않았고, 같은 색이어야 한다.

만약 다음 정점이 이미 방문한 점이라면 이때 사이클인지 아닌지를 판별하는데, 한 점에서 dfs를 돌릴 때, depth의 차이가 1이라면 양방향 간선에 의해 바로 이전 정점을 방문하는 경우이고, depth차이가 2인 경우는 나올 수 없고, 3 이상 차이 나는 경우가 바로 사이클인 경우이다. depth가 3 이상 차이나는 경우를 찾아야 하므로, bfs가 아닌 dfs로 풀어야 하고, 방문 체크 배열 visited는 true/false가 아닌 depth를 저장한다.

 

2022-06-23

이전에 했던 방식은 visited에 depth를 저장해 이전 방문한 칸을 바로 다시 방문하는 경우를 걸러주었다.

이번에 푼 방식은(코드2) 이전 노드에서의 방향을 가지고 있다가 현재 방향과 2가 차이나면 스킵하는 것으로 이전 방문한 칸을 바로 다시 방문하는 경우를 걸러주었다.

방향을 우,상,좌,하 순으로 두었고, 방향 차이가 2라면 역방향으로 가는 것을 의미하고, 역방향은 바로 이전 칸에 다시 방문하려는 것을 의미한다. 

 

 

코드1

val br = System.`in`.bufferedReader()

lateinit var visited: Array<IntArray>
lateinit var graph: Array<String>
val dir = arrayOf(
    arrayOf(0,1),
    arrayOf(1,0),
    arrayOf(0,-1),
    arrayOf(-1,0)
)
var answer=  false

fun dfs(depth: Int, r: Int, c: Int,n: Int,m: Int){
    visited[r][c] = depth
    for(i in 0 until 4){
        val nr = r + dir[i][0]
        val nc = c + dir[i][1]
        if(nr !in 0 until n || nc !in 0 until m) continue
        if(graph[nr][nc] != graph[r][c]) continue
        if(visited[nr][nc]<0){
            dfs(depth+1, nr, nc, n, m )
        }
        else{
            if(visited[r][c]-visited[nr][nc]>=3){
                answer = true
                return
            }
        }
    }
}

fun main() = with(System.out.bufferedWriter()){

    //input
    val (n,m) = br.readLine().split(' ').map{it.toInt()}
    visited= Array(n){ IntArray(m){-1} }
    graph = Array(n){br.readLine()}

    //solve
    label@for(r in 0 until n){
        for(c in 0 until m){
            if(visited[r][c]==-1){
                dfs(0,r,c,n,m)
                if(answer) break@label
            }
        }
    }
    write(if(answer) "Yes" else "No")

    close()
}

코드2

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()
lateinit var graph: Array<String>
lateinit var visited: Array<BooleanArray>

val dir = arrayOf(
    arrayOf(0,1),
    arrayOf(1,0),
    arrayOf(0,-1),
    arrayOf(-1,0)
)
var answer = "No"
fun dfs(r: Int, c: Int, d: Int, n: Int, m: Int){

    visited[r][c] = true

    for(i in 0 until 4){
        val nr = r+dir[i][0]
        val nc = c+dir[i][1]
        if(nr !in 0 until n || nc !in 0 until m) continue
        if(Math.abs(d-i)==2) continue
        if(graph[nr][nc] != graph[r][c]) continue
        if(visited[nr][nc]){
            answer ="Yes"
            return
        }
        dfs(nr,nc,i, n, m)
        if(answer=="Yes") return
    }
}

fun main() = with(System.out.bufferedWriter()){
    //input
    val (n,m) = getIntList()
    graph = Array(n){br.readLine()}
    visited = Array(n){BooleanArray(m)}
    //solve
    for(i in 0 until n){
        for(j in 0 until m){
            if(visited[i][j]) continue
            dfs(i,j,-10,n,m)
        }
    }
    //output
    write("$answer")

    close()
}