백준 16724 피리 부는 사나이 Kotlin (dfs,유니온파인드)

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

16724번: 피리 부는 사나이

문제

피리 부는 사나이 성우는 오늘도 피리를 분다.

성우가 피리를 불 때면 영과일 회원들은 자기도 모르게 성우가 정해놓은 방향대로 움직이기 시작한다. 성우가 정해놓은 방향은 총 4가지로 U, D, L, R이고 각각 위, 아래, 왼쪽, 오른쪽으로 이동하게 한다.

이를 지켜보던 재훈이는 더 이상 움직이기 힘들어하는 영과일 회원들을 지키기 위해 특정 지점에 ‘SAFE ZONE’ 이라는 최첨단 방음 시설을 만들어 회원들이 성우의 피리 소리를 듣지 못하게 하려고 한다. 하지만 예산이 넉넉하지 않은 재훈이는 성우가 설정해 놓은 방향을 분석해서 최소 개수의 ‘SAFE ZONE’을 만들려 한다. 

성우가 설정한 방향 지도가 주어졌을 때 재훈이를 도와서 영과일 회원들이 지도 어느 구역에 있더라도 성우가 피리를 불 때 ‘SAFE ZONE’에 들어갈 수 있게 하는 ‘SAFE ZONE’의 최소 개수를 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다.

두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주어진다.

지도 밖으로 나가는 방향의 입력은 주어지지 않는다.

출력

첫 번째 줄에 ‘SAFE ZONE’의 최소 개수를 출력한다.

알고리즘 분류

• 그래프 이론
• 자료 구조
• 그래프 탐색
• 깊이 우선 탐색
• 분리 집합

풀이

2021.11.26 - [알고리즘 문제 풀이/백준] - 백준 17090 미로 탈출하기 Kotlin (dfs,bfs)

위의 문제와 비교해보길 추천!

 

dfs + 유니온 파인드

dfs + 메모이제이션

두 가지 풀이가 있다.

우선 문제를 해석하면,

한 사이클마다 하나의 SAFE ZONE이 나오므로,

사이클의 개수를 찾는 것이 관건이다.

 

dfs + 유니온 파인드는,

모든 노드를 시작점으로 dfs로 탐색하며, parent를 합쳐준다.

parent가 같은 노드를 만나면 사이클 완성!

 

이후, set을 이용해 사이클의 개수를 세면 되는데, parent 배열에서 아직 parent가 본인의 사이클로 갱신되지 않은 경우가 있을 수 있기 때문에 parent[i]가 아닌 getParent(parent[i])를 set에 저장하는 것을 잊지 말자.

 

dfs + 메모이제이션은,

사이클의 번호를 매기고,

dfs를 이용해 사이클을 만들어 나간다.

한 번의 dfs에서 나올 수 있는 경우는,

현재 dfs로 탐색한 경로에 다시 돌아오는 경우 -> 새로운 사이클 탄생

이미 만들어진 사이클에 들어가는 경우 -> 기존 사이클에 현재 경로를 병합

두 가지 경우가 있다.

 

이를 구현하는 방법은, 사이클의 번호를 1부터 시작하여 모든 노드에 대해 dfs를 시작한다. (이미 방문한 노드는 스킵)

dfs의 끝부분이 현재 탐색한 경로에 다시 돌아오는 경우는 현재 사이클 번호를 그대로 현재 탐색한 경로들의 visited 에 저장하고, dfs의 끝부분이 이미 만들어진 사이클에 들어가는 경우 이미 만들어진 사이클의 번호를 현재 탐색한 경로들의 visited에 저장한다.

 

코드(유니온파인드)

//1<=n,m<=1000

val dir = mapOf(
    'D' to Pair(1,0),
    'U' to Pair(-1,0),
    'L' to Pair(0,-1),
    'R' to Pair(0,1)
)
val parent = IntArray(1000000){it}

fun getParent(idx : Int) : Int{
    if(parent[idx] ==idx) return parent[idx] else return getParent(parent[idx]).also{parent[idx]= it}
}

fun unionParent(a : Int, b : Int){
    val aa = getParent(a)
    val bb = getParent(b)
    if(aa<bb){
        parent[bb] = aa
    }
    else{
        parent[aa] = bb
    }
}

fun findParent(a : Int, b : Int) : Boolean{
    val aa = getParent(a)
    val bb = getParent(b)
    return aa==bb
}


fun dfs(r : Int, c : Int, n : Int, m : Int, graph: Array<String>){
    val nr = r + dir[graph[r][c]]!!.first
    val nc = c + dir[graph[r][c]]!!.second
    val curIdx = r*m+c
    val nextIdx = nr*m+nc
    //유니온 파인드로 사이클 찾기
    //사이클이 완성된다면 리턴
    if(findParent(curIdx,nextIdx)) return
    unionParent(curIdx,nextIdx)
    dfs(nr,nc,n,m,graph)
}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val (n,m) = br.readLine().split(' ').map{it.toInt()}
    val graph = Array<String>(n){""}
    for(i in 0 until n){
        graph[i] = br.readLine()
    }
	//dfs로 그래프 탐색
    for(i in 0 until n){
        for(j in 0 until m){
            dfs(i,j,n,m,graph)
        }
    }
    
    //사이클 개수 카운트
    val answer = mutableSetOf<Int>()
    for(i in 0 until n*m){
        answer.add(getParent(parent[i]))
    }

    write("${answer.size}")
    close()
}

코드(dfs)

//1<=n,m<=1000

val dir = mapOf(
    'D' to Pair(1,0),
    'U' to Pair(-1,0),
    'L' to Pair(0,-1),
    'R' to Pair(0,1)
)
val visited = Array(1000){IntArray(1000)}
var cycle=1
fun dfs(r : Int, c : Int, n : Int, m : Int, graph: Array<String>) : Int{
    val nr = r + dir[graph[r][c]]!!.first
    val nc = c + dir[graph[r][c]]!!.second
    if(visited[nr][nc]!=0){
        return visited[nr][nc]
    }
    visited[nr][nc]=cycle
    visited[nr][nc] =dfs(nr,nc,n,m,graph)

    return 1
}

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val (n,m) = br.readLine().split(' ').map{it.toInt()}
    val graph = Array<String>(n){""}
    for(i in 0 until n){
        graph[i] = br.readLine()
    }

    for(i in 0 until n){
        for(j in 0 until m){
            if(visited[i][j]!=0) continue
            visited[i][j]=cycle
            visited[i][j]=dfs(i,j,n,m,graph)
            cycle++
        }
    }
    val answer = mutableSetOf<Int>()
    for(i in 0 until n){
        for(j in 0 until m){
            answer.add(visited[i][j])
        }
    }
    
    write("${answer.size}")
    close()
}