백준 17070 파이프 옮기기 Kotlin

안녕하세요!

오늘은 백준 파이프 옮기기 문제를 풀어봤습니다!

 

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

17070번: 파이프 옮기기 1

 

이 문제는 그래프 탐색 문제입니다

저는 처음에 BFS 로 풀었는대 BFS로 풀면 시간 초과가 뜹니다 이유는 정확히 잘 모르겠지만 

DFS로 풀면 쉽게 풀수 있는 문제 입니다

 

각 파이프의 오른쪽 끝에 좌표와 해당 파이프의 놓여진 방향을 저장 해 놓고

다음에 놓여진 방향에 따른  파이프의 좌표와 놓여진 방향을 DFS를 이용해서 (N,N) 까지 찾아 들어가면 되는 문제입니다!

import java.util.*


var arr : Array<IntArray> = arrayOf()
private var  N = 0
var ans = 0
class Point(var x : Int , var y : Int , var shape : String)
fun dfs(point: Point){
    if(point.x==N-1 &&
        point.y==N-1){
        ans++
    }else{
        if(point.shape=="w"){


            if(point.y+1<N){

                if(arr[point.x][point.y+1]!=1){
                    dfs(Point(point.x,point.y+1,"w"))
                }
            }

            if(point.y+1<N && point.x+1<N){

                if(arr[point.x+1][point.y+1]!=1 &&
                    arr[point.x][point.y+1]!=1 &&
                    arr[point.x+1][point.y]!=1){
                    dfs(Point(point.x+1,point.y+1,"c"))
                }
            }

        }else if(point.shape=="h"){


            if(point.x+1<N){

                if(arr[point.x+1][point.y]!=1){
                    dfs(Point(point.x+1,point.y,"h"))
                }
            }

            if(point.y+1<N && point.x+1<N){

                if(arr[point.x+1][point.y+1]!=1 &&
                    arr[point.x][point.y+1]!=1 &&
                    arr[point.x+1][point.y]!=1){
                    dfs(Point(point.x+1,point.y+1,"c"))
                }
            }


        }else{


            if(point.y+1<N && point.x+1<N){

                if(arr[point.x+1][point.y+1]!=1 &&
                    arr[point.x][point.y+1]!=1 &&
                    arr[point.x+1][point.y]!=1){
                    dfs(Point(point.x+1,point.y+1,"c"))
                }
            }

            if(point.y+1<N){

                if(arr[point.x][point.y+1]!=1){
                    dfs(Point(point.x,point.y+1,"w"))
                }
            }

            if(point.x+1<N){

                if(arr[point.x+1][point.y]!=1){
                    dfs(Point(point.x+1,point.y,"h"))
                }
            }
        }
    }

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

     N = readLine()!!.toInt()

    arr = Array(N){ IntArray(N) }

    for(i in 0 until N){

        var str = readLine()!!.split(" ")

        for(j in str.indices){
            arr[i][j] = str[j].toInt()
        }
    }

dfs(Point(0,1,"w"))

    println(ans)


}