[백준 17070번][Kotlin] 파이프 옮기기 1

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

17070번: 파이프 옮기기 1

 

난이도 : 골드 5
태그 : 그래프 탐색, 그래프 이론, 다이나믹 프로그래밍

 

 

설명

DFS를 사용하여, 직전 파이프의 형태 (가로, 세로, 대각선)을 참고하여

풀이할 수 있는 문제입니다.

 

처음엔 DFS 없이 DP만을 사용하여 풀이하려고 했으나,

생각보다 잘 되지 않아서, 마침내 그래프 탐색 문제인걸 깨닫고 푼 문제였습니다.

 

 

소스코드

전체 소스코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer

enum class Direction { VERTICAL, HORIZONTAL, DIAGONAL }

private lateinit var map: Array<Array<Int>>
var n = 0
var cnt = 0

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    n = br.readLine().toInt()
    map = Array(n) { Array(n) { 0 } }

    repeat(n) { x ->
        val st = StringTokenizer(br.readLine(), " ")
        repeat(n) { y ->
            map[x][y] = st.nextToken().toInt()
        }
    }

    dfs(0, 1, Direction.HORIZONTAL)
    println(cnt)
}

fun dfs(x: Int, y: Int, direction: Direction) {
    if (x >= n || y >= n || map[x][y] == 1 ||
        (direction == Direction.DIAGONAL && (map[x - 1][y] == 1 || map[x][y - 1] == 1))
    ) return

    if (x == n - 1 && y == n - 1) {
        cnt++
        return
    }

    when (direction) {
        Direction.HORIZONTAL -> {
            dfs(x, y + 1, Direction.HORIZONTAL)
            dfs(x + 1, y + 1, Direction.DIAGONAL)
        }

        Direction.VERTICAL -> {
            dfs(x + 1, y, Direction.VERTICAL)
            dfs(x + 1, y + 1, Direction.DIAGONAL)
        }

        Direction.DIAGONAL -> {
            dfs(x, y + 1, Direction.HORIZONTAL)
            dfs(x + 1, y, Direction.VERTICAL)
            dfs(x + 1, y + 1, Direction.DIAGONAL)
        }
    }
}

 

전체 소스코드 입니다. 하나씩 살펴보겠습니다.

 

 

 

enum 클래스 Direction 생성

enum class Direction { VERTICAL, HORIZONTAL, DIAGONAL }

방향을 담을 enum class 입니다. 수직, 수평, 대각선 세 방향이 있습니다.

굳이 enum 클래스를 사용하지 않고, 상태를 0, 1, 2와 같이 Int형을 사용해 나타내도 되지만,

저는 상태를 저장할때 0, 1, 2를 사용해 나타내면 나중에 코드를 볼때 헷갈려 하는 편이라...(ㅠㅠ)

enum 클래스를 사용하였습니다.

 

 

 

Map 초기화

val br = BufferedReader(InputStreamReader(System.`in`))
n = br.readLine().toInt()
map = Array(n) { Array(n) { 0 } }

repeat(n) { x ->
    val st = StringTokenizer(br.readLine(), " ")
    repeat(n) { y ->
        map[x][y] = st.nextToken().toInt()
    }
}

 

n과 map을 입력받고, 초기화하는 부분입니다.

 

 

DFS

fun dfs(x: Int, y: Int, direction: Direction) {
    if (x >= n || y >= n || map[x][y] == 1 ||
        (direction == Direction.DIAGONAL && (map[x - 1][y] == 1 || map[x][y - 1] == 1))
    ) return

    if (x == n - 1 && y == n - 1) {
        cnt++
        return
    }

    when (direction) {
        Direction.HORIZONTAL -> {
            dfs(x, y + 1, Direction.HORIZONTAL)
            dfs(x + 1, y + 1, Direction.DIAGONAL)
        }

        Direction.VERTICAL -> {
            dfs(x + 1, y, Direction.VERTICAL)
            dfs(x + 1, y + 1, Direction.DIAGONAL)
        }

        Direction.DIAGONAL -> {
            dfs(x, y + 1, Direction.HORIZONTAL)
            dfs(x + 1, y, Direction.VERTICAL)
            dfs(x + 1, y + 1, Direction.DIAGONAL)
        }
    }
}

 

dfs를 수행하는 부분입니다.

 

파이프는 45도 씩만 회전할 수 있으므로,

직전의 direction이 뭐였는지에 따라,

 

직전 파이프가 수평일땐 대각선, 수평을,

직전 파이프가 수직일땐 대각성, 수직을,

직전 파이프가 대각선일땐 모든 형태에 대해 재귀적으로 dfs를 수행합니다.

 

수평일 경우에는 y를 1만큼,

수직일 경우엔 x를 1만큼,

대각선일 경우엔 x, y 모두를 1만큼 증가시켜 매개변수로 넘겨줍니다.

 

 

 

if (x >= n || y >= n || map[x][y] == 1 ||
    (direction == Direction.DIAGONAL && (map[x - 1][y] == 1 || map[x][y - 1] == 1))
) return

이 부분은 x, y 범위와 사용 가능한 칸인지 확인하는 부분입니다.

x, y중 하나라도 n보다 같거나 커진다면 해당 탐색 종료.

 

수평, 수직일 경우 해당 좌표가 1이라면 탐색 종료.

 

대각선일 경우 해당 좌표와, 위쪽, 아래쪽 좌표를 검사해 1일 경우 탐색을 종료합니다.

 

 

if (x == n - 1 && y == n - 1) {
    cnt++
    return
}

 

위 if문이 후,

x와 y가 n-1에 도달할때마다 cnt를 증가시키고 탐색을 종료합니다.

 

 

 

후기

그래프 탐색을 쉽게 떠올리지 못해

DFS 없이 DP만으로 풀려다가 꽤 애먹은 문제였습니다.

문제를 보고 어떤 유형인지 딱 떠올리는 연습이 필요한 것 같네요