BOJ(백준) 1952번 달팽이2



문제 : M줄 N칸의 Matrix에 달팽이가 (0,0)부터 돌았을 때 몇 번 방향을 꺾는지 확인하는 문제다.


매우 쉬운 문제지만, 나의 코드의 1/3밖에 안되지만 속도도 더 빠른 BOJ id tncks0121님의 코드를 소개하고자 글을 쓴다.


 먼저 나의 코드는 아래와 같다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
fun main(args: Array<String>) {
    val (r,c)= readLine()!!.split(' ').map { it.toInt() }
    val map=Array(r){IntArray(c)}
    val dx= arrayOf(0,1,0,-1)
    val dy= arrayOf(1,0,-1,0)
    var res=0
    var count=1

    fun go(x:Int,y:Int,dir:Int){
        map[x][y]=count++
        val bx=x+dx[dir]
        val by=y+dy[dir]
        if(bx in 0 until r && by in 0 until c && map[bx][by]==0){
            go(bx, by, dir)
        }
        else{
            res++
            if(map[x+dx[(dir+1)%4]][y+dy[(dir+1)%4]]==0)
               go(x+dx[(dir+1)%4],y+dy[(dir+1)%4],(dir+1)%4)
        }
    }
    map[0][0]=1
    go(0,0,0)
    println(res-1)
}
cs


 나의 코드 개념은 처음(0,0)부터 돌면서 matrix에 다 숫자를 써준다는 것이다. 

tncks님의 코드를 보고 감탄을 할 정도로 내 코드는 역겨웠다....



 다음은 tncks0121님의 코드이다.


1
2
3
4
5
6
7
8
9
10
11
12
fun main(args: Array<String>) {
  fun go(n: Int, m: Int): Int = when {
    n == 1 -> 0
    m == 1 -> 1
    n == 2 -> 2
    m == 2 -> 3
    else -> 4 + go(n - 2, m - 2) 
  }
  val (M, N) = readLine()!!.split(" ").map{ it.toInt() }
  println(go(M, N))
}
cs


  go 함수를 파헤쳐보자...

 go함수 내부의 when절 내부에 else문을 보면 4 + go(n-2, m-2) 로 되어있는데

이것은 한바퀴 돌았다는 것을 의미한다.  4 = 방향을 4번 바꿨다 = 한바퀴 돌았다. 

그리고 n과 m을 2씩 줄여서 재귀함수를 돌린다. 왜냐하면 한바퀴 돌면  Matrix의 행과 열의 양끝을 돈 것이므로...


이제 else위의 경우를 하나하나씩 살펴보자.

 n == 1 -> 0   : 이것은 row(행)가 1개밖에 없는 것으로  col(열)이 몇개가 되든 우측 방향으로 가기만 하면 끝난다는 생각이므로 , 0을 return하게 하였다.


 m == 1 -> 1    : 이것은 col이 1개밖에 없는 것으로 1을 return한다. 이유는 재귀를 돌고나면 우측방향으로 돌고있다고 생각하기 때문에(처음에 시작이 오른쪽 방향임), 그런데 현재 col이 1이므로 아래 방향으로 가야한다 = 한번 방향 전환을 해야함. 따라서 1을 return 한다.


 n == 2 -> 2   : 이 것은 row가 2인 상황이다. 위에 내용을 이해 했다면 왜 2를 return 하는지 알 수 있다.

한번 더 설명하자면, row가 2인 경우 col의 크기에 상관없이 방향 전환을  ( 우측 상단 끝, 우측 하단 끝) 이렇게 2번 하면 된다. 따라서 2를 return 한다.


 m == 2 -> 3 : 이 설명은 생략한다.



 

 결론 : 내 코드는 Matrix의 모든 Point를 다 돌아보도록 짰는데, 이 코드는 재귀를 몇번 돌지도 않는다.....



 

 일단 내가 판단하기에 잘 짰다고 생각해서 코드를 보고 퍼왔다. tncks님이 이 글을 보신다면 댓글좀요.

코틀린 좀 가르쳐줘요.

저작자표시

'BOJ(백준)' 카테고리의 다른 글

[BOJ] 백준 9576번 책 나눠주기  (0) 2018.11.22
[BOJ] 백준 11066번 파일 합치기 by Kotlin  (0) 2018.11.21
[BOJ] 백준 5397번 키로거 by Kotlin  (0) 2018.11.20
[BOJ] 백준 8983번 사냥꾼 by Kotlin  (0) 2018.11.20
[BOJ] 2170번 선 긋기 by Kotlin  (0) 2018.11.13

백준 9576번 : 책 나눠주기



 설명: 이 문제를 처음에는 이분매칭으로 풀려고 하다가, 이분매칭보다는 그냥 Greedy하게 풀면 풀리겠다고 생각해서

      그리디로 해결하였다.


    List에 사람 각각의 (a,b)를 Pair로 저장해준다. 그리고 Sorting한다.

Sorting의 기준은 b의 오른차순으로 정렬했으며, b가 똑같은 경우 a가 작은 것이 앞에 오도록 정렬하였다.


(만약 input이 

1                이라면 소팅 된 후의 값은   

5 5 (n,m)           

2 4                            1 2

3 4                           1 3

3 3                           3 3

1 2                           2 4

1 3                           3 4

)

 정렬 후 List의 처음부터 한명씩 확인한다.

그리고 그 사람의 a와 b사이를 확인하면서 가져갈 수 있는 책이 존재하면 가져가도록 하고

그 index의 visit을 true로 바꿔준다.


 핵심은 정렬의 기준을 잡고 정렬 후 이중for문을 돌면서 확인해서 책을 가져가는 것이라고 생각한다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.io.BufferedReader
import java.io.InputStreamReader

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    data class Pair(val s: Int, val e: Int) : Comparable<Pair> {
        override fun compareTo(other: Pair): Int {
            if (this.e != other.e) return this.e - other.e
            return this.s - other.s
        }
    }
    repeat(br.readLine()!!.toInt()) {
        val (n, m) = br.readLine()!!.split(" ").map { it.toInt() }
        val list = Array(m) {
            val (s, e) = br.readLine()!!.split(" ").map { it.toInt() - 1 }
            Pair(s, e)
        }
        list.sort()
        
        val visit = BooleanArray(n)
        var res = 0
        for (i in 0 until m) {
            for (j in list[i].s..list[i].e) {
                if (!visit[j]) {
                    visit[j] = true
                    res++
                    break
                }
            }
        }
        println(res)
    }
}
cs









저작자표시

'BOJ(백준)' 카테고리의 다른 글

[BOJ] 1952번 달팽이2  (0) 2018.12.31
[BOJ] 백준 11066번 파일 합치기 by Kotlin  (0) 2018.11.21
[BOJ] 백준 5397번 키로거 by Kotlin  (0) 2018.11.20
[BOJ] 백준 8983번 사냥꾼 by Kotlin  (0) 2018.11.20
[BOJ] 2170번 선 긋기 by Kotlin  (0) 2018.11.13

DP문제.


점화식은    dp[i][j] => i~j 까지의 최소 비용

dp[i][j]= min(dp[i][j], dp[i][k] + dp[k+1][j])    => 합친 값의 최소값을 선택. k는 i와 j의 사이값들 모두 확인해야한다.

dp[i][j]+=sum[j]-sum[j-1]   (i부터 j까지의 합 추가로 더해줘야함)


O(n^3)


문제 바로가기 : boj.kr/11066


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.io.BufferedReader
import java.io.InputStreamReader
import kotlin.math.min

fun main(args: Array<String>) {
    val br= BufferedReader(InputStreamReader(System.`in`))
    
repeat(br.readLine()!!.toInt()){
        val n=br.readLine()!!.toInt()
        val arr=br.readLine()!!.split(" ").map { it.toInt() }.toIntArray()
        val dp=Array(n){IntArray(n)}
        val sum=IntArray(n)
        sum[0]=arr[0]
        for(i in 1 until n)  sum[i]=sum[i-1]+arr[i]
        
        for(j in 1 until n){
            for(i in j-1 downTo 0){
                dp[i][j]=987654321
                for(k in i until j){
                    dp[i][j]= min(dp[i][j],dp[i][k]+dp[k+1][j])
                }
                if(i!=0)    dp[i][j]+=sum[j]-sum[i-1]
                else    dp[i][j]+=sum[j]
            }
        }
        println(dp[0][n-1])
    }
}
cs


저작자표시

'BOJ(백준)' 카테고리의 다른 글

[BOJ] 1952번 달팽이2  (0) 2018.12.31
[BOJ] 백준 9576번 책 나눠주기  (0) 2018.11.22
[BOJ] 백준 5397번 키로거 by Kotlin  (0) 2018.11.20
[BOJ] 백준 8983번 사냥꾼 by Kotlin  (0) 2018.11.20
[BOJ] 2170번 선 긋기 by Kotlin  (0) 2018.11.13

결과를 StringBuilder로 안하고 +로 하여 시간초과가 계속 나서 고생했던 문제.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    repeat(br.readLine()!!.toInt()) {
        val str = br.readLine()!!
        val res = LinkedList<Char>()
        var now = 0
        for (i in 0 until str.length) {
            when (str[i]) {
                '<' -> if (now != 0) now--
                '>' -> if (now != res.size) now++
                '-' -> if (now != 0 && !res.isEmpty()) res.removeAt(--now)
                else -> res.add(now++, str[i])
            }
        }
        val ans = StringBuilder()
        for (ch in res) {
            ans.append(ch)
        }
        println(ans)
    }
}
cs


저작자표시

'BOJ(백준)' 카테고리의 다른 글

[BOJ] 백준 9576번 책 나눠주기  (0) 2018.11.22
[BOJ] 백준 11066번 파일 합치기 by Kotlin  (0) 2018.11.21
[BOJ] 백준 8983번 사냥꾼 by Kotlin  (0) 2018.11.20
[BOJ] 2170번 선 긋기 by Kotlin  (0) 2018.11.13
[BOJ] 1017번 소수 쌍 by Kotlin  (0) 2018.10.07



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.io.BufferedReader
import java.io.InputStreamReader


fun main(args: Array<String>) {
    val br=BufferedReader(InputStreamReader(System.`in`))
    val (m,n,l)=br.readLine()!!.split(" ").map { it.toInt() }
    val saro=br.readLine()!!.split(" ").map { it.toInt() }.sorted()
    val animal=Array(n){ val (x,y)=br.readLine()!!.split(" ").map { it.toInt() }
        Pair(x,y) }
    var res=0

    for(i in 0 until n){
        val (x,y)=animal[i]
        if(y>l) continue    // y값이 l보다 커지면 사대의 x좌표에 상관없이 도달 할 수 없음.
        var left=0
        var right=m-1
        while(left<=right){     // 동물의 x좌표를 가지고 사대를 이진탐색
            val mid=(left+right)/2
            if(saro[mid] in x-(l-y)..x+(l-y)){  // 동물의 x좌표에서 양옆으로 (l-y)만큼 떨어져있으면
//사냥가능하다
                res++
                break
            }
            if(saro[mid]<x-(y-l))   left=mid+1
            else    right=mid-1
        }
    }
    println(res)
}

cs


저작자표시

'BOJ(백준)' 카테고리의 다른 글

[BOJ] 백준 11066번 파일 합치기 by Kotlin  (0) 2018.11.21
[BOJ] 백준 5397번 키로거 by Kotlin  (0) 2018.11.20
[BOJ] 2170번 선 긋기 by Kotlin  (0) 2018.11.13
[BOJ] 1017번 소수 쌍 by Kotlin  (0) 2018.10.07
[BOJ] 1671번 상어의 저녁식사 by Kotlin  (0) 2018.10.06

백준 2170번 선 긋기


문제 바로가기 : boj.kr/2170



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.io.BufferedReader
import java.io.InputStreamReader

fun main(args: Array<String>) {
    val br=BufferedReader(InputStreamReader(System.`in`))
    val n=br.readLine()!!.toInt()
    data class Pair(val start:Int,val end:Int):Comparable<Pair>{
        override fun compareTo(other: Pair): Int {
            return this.start.compareTo(other.start)
        }
    }
    val line=Array(n){ val (start,fin)=br.readLine()!!.split(" ").map { it.toInt() }
        Pair(start,fin)
    }
    line.sort()
    var now=line[0].start
    var res=0
    for(i in 0 until n){
        if(line[i].end>now){
            res += if(now>=line[i].start) {
                Math.abs(line[i].end - now)
            } else{
                Math.abs(line[i].end-line[i].start)
            }
            now = line[i].end
        }
    }
    println(res)
}
cs


저작자표시

'BOJ(백준)' 카테고리의 다른 글

[BOJ] 백준 5397번 키로거 by Kotlin  (0) 2018.11.20
[BOJ] 백준 8983번 사냥꾼 by Kotlin  (0) 2018.11.20
[BOJ] 1017번 소수 쌍 by Kotlin  (0) 2018.10.07
[BOJ] 1671번 상어의 저녁식사 by Kotlin  (0) 2018.10.06
[BOJ] 1021번 회전하는 큐 - by Kotlin  (0) 2018.10.02

백준 1017번 소수 쌍


문제 설명


 각 수에 대해 다른 수와 합이 소수이면 선택 가능하도록 간선을 만들어준다.

그리고 첫번째 수에 가능한 수를 하나씩 고정시켜놓고, 나머지를 이분매칭 시켜서 모두 매칭이 되면 res에 추가.

 

 1) 두 수의 합이 최대 2000까지이므로 에라토스테네스의 체로 2000까지 Boolean Array로 감별

 

 2) 하나의 숫자에 대해 다른 숫자와의 합이 소수이면 간선 추가.


 3) adj[0][0] , adj[0][1] ... adj[0][adj.size-1] 에 대해

 각각 B[adj[0][i]]=0 (즉, 첫번째 수와 i번째 수를 매칭시킴)

 그리고 나머지에 대해 이분매칭 



문제 바로가기 : boj.kr/1017


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main(args: Array<String>) {
    val br= BufferedReader(InputStreamReader(System.`in`))
    val n=br.readLine()!!.toInt()
    val arr=br.readLine()!!.split(" ").map { it.toInt() }
    val chkPrimeNum=BooleanArray(2001){true}
    val adj=Array(n){ LinkedList<Int>() }
    val visit=BooleanArray(n)
    val B=IntArray(n){-1}

    chkPrimeNum[1]=false
    for(i in 2..2000){ // 에라토스테네스의 체로 2000까지
        var j=2
        if(chkPrimeNum[i]) {
            while (i * j <= 2000) {
                chkPrimeNum[i*j]=false
                j++
            }
        }
    }

    for(i in 0 until n){ //간선 연결
        for(j in 0 until n){
            if(i==j)    continue
            if(chkPrimeNum[arr[i]+arr[j]]){
                adj[i].add(j)
            }
        }
    }

    fun go(here:Int):Boolean{
        if(visit[here]) return false
        visit[here]=true
        for(there in adj[here]){
            if(B[there]==-1||go(B[there])){
                B[there]=here
                return true
            }
        }
        return false
    }

    val res=LinkedList<Int>()
    for(i in 0 until adj[0].size){
        B.fill(-1)
        B[adj[0][i]]=0
        var count=1
        for(j in 1 until n){
            visit.fill(false)
            visit[0]=true
            if(go(j))   count++
            else break
        }
        if(count==n) res.add(arr[adj[0][i]])
    }
    if(res.isEmpty())   println(-1)
    else{
        res.sort()
        println(res.joinToString(" "))
    }
}

cs









저작자표시

'BOJ(백준)' 카테고리의 다른 글

[BOJ] 백준 8983번 사냥꾼 by Kotlin  (0) 2018.11.20
[BOJ] 2170번 선 긋기 by Kotlin  (0) 2018.11.13
[BOJ] 1671번 상어의 저녁식사 by Kotlin  (0) 2018.10.06
[BOJ] 1021번 회전하는 큐 - by Kotlin  (0) 2018.10.02
[BOJ] 1068번 트리 byKotlin  (0) 2018.10.02

백준 1671번 상어의 저녁식사.


문제 설명

 

 크기, 속도, 지능 모두 크거나 같으면  i -> j 가 먹을 수 있다.  =  "i 에서 j로 갈 수 있다" 

즉, 먹을 수 있는 간선들을 모두 만들면 이분 매칭 문제와 같다.

 

 주의할 점은 크기, 속도, 지능 모두 같으면 서로 잡아먹어서 0이 될 수도 있으므로

상어 한마리가 또다른 한마리만 먹을 수 있도록 설정했다.

 ex)  크기: 10 속도:10 지능:10 인 상어 2마리(i,j) 가 있을 때  i는 j를 잡아 먹을 수 있지만 j는 i를 잡아먹지 못하도록 설정했다.



문제 바로가기 : boj.kr/1671



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main(args: Array<String>) {
    data class Shark(val size:Int,val speed:Int,val intel:Int):Comparable<Shark>{
        override fun compareTo(other: Shark): Int {
            if(size==other.size&&speed==other.speed&&intel==other.intel)    return 0
            if(size>=other.size&&speed>=other.speed&&intel>=other.intel)    return 1
            return -1
        }
    }
    val br=BufferedReader(InputStreamReader(System.`in`))
    val list=ArrayList<Shark>()
    val n=br.readLine()!!.toInt()
    var visit=BooleanArray(n)
    val B=IntArray(n){-1}
    val adj=Array(n){ LinkedList<Int>() }
    repeat(n){
        val (size,speed,intel)=br.readLine()!!.split(" ").map { it.toInt() }
        list.add(Shark(size,speed,intel))
    }
    
    for(i in 0 until n){
        for(j in 0 until n){
            if(i==j)    continue
            if(list[i]==list[j]&&i>j){
                adj[i].add(j)
            }
            else if(list[i]>list[j]){
                adj[i].add(j)
            }
        }
    }
    
    fun go(here:Int):Boolean{
        if(visit[here]) return false
        visit[here]=true
        for(there in adj[here]){
            if(B[there]==-1||go(B[there])){
                B[there]=here
                return true
            }
        }
        return false
    }
    
    var count=0
    for(i in 0 until n){
        visit.fill(false)
        if(go(i))   count++
        visit.fill(false)
        if(go(i))   count++
    }
    println(n-count)
}
cs


저작자표시

'BOJ(백준)' 카테고리의 다른 글

[BOJ] 2170번 선 긋기 by Kotlin  (0) 2018.11.13
[BOJ] 1017번 소수 쌍 by Kotlin  (0) 2018.10.07
[BOJ] 1021번 회전하는 큐 - by Kotlin  (0) 2018.10.02
[BOJ] 1068번 트리 byKotlin  (0) 2018.10.02
BOJ 2789번 유학금지 by Kotlin  (0) 2018.07.18

[BOJ] 1021번 회전하는 큐


문제 : 원형 큐에서 현재 위치에서 목적 위치까지 가는데 가장 가까운 방법으로 가는데 드는 비용의 합.



설명 : 큐에 1~N까지 원소를 넣고,  현재 위치는 큐의 첫번째 원소로 생각.

  ( 큐의 첫번째 위치에서 +1 ,  큐의 끝점에서 -1 ) => 반복해서 도착하고자 하는 번호에 먼저 도달하는 것이 비용이 작게 든다. 따라서 먼저 도달한 방법으로   큐의 현재위치(q[0]) 를 이동시킨다.


 만약 현재위치에서 좌측으로 가는 것이 빠르다 => q[0]에 큐의 마지막 원소를 넣고, 마지막 원소를 삭제 : 즉, 좌측으로 이동.

 만약 현재위치에서 우측으로 가는 것이 빠르다 => 큐에 q[0]를 뒤에 추가하고, q[0]를 삭제 : 즉 q[0]를 우측으로 이동

 

 그리고 한칸이동 시 비용을  +1 해주어서 결과값을 얻었다.



(문제 바로가기 : https://boj.kr/1021 )


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (n, m) = br.readLine()!!.split(" ").map { it.toInt() }
    val choice = br.readLine()!!.split(" ").map { it.toInt() }.toIntArray()
    val q = LinkedList<Int>()
    for (i in 1..n) q.add(i)
    var res = 0
    var count = 0
    while (count != m) {
        if (q.first == choice[count]) {
            q.poll()
        } 
        else {
            for (i in 1 until q.size) {
                if (q[q.size - i] == choice[count]) {
                    while (q[0] != choice[count]) {
                        q.add(0, q.last)
                        q.removeLast()
                        res++
                    }
                    q.poll()
                    break
                } else if (q[i] == choice[count]) {
                    while (q[0] != choice[count]) {
                        q.add(q.first)
                        q.removeFirst()
                        res++
                    }
                    q.poll()
                    break
                }
            }
        }
        count++
    }
    println(res)
}
cs




저작자표시

'BOJ(백준)' 카테고리의 다른 글

[BOJ] 2170번 선 긋기 by Kotlin  (0) 2018.11.13
[BOJ] 1017번 소수 쌍 by Kotlin  (0) 2018.10.07
[BOJ] 1671번 상어의 저녁식사 by Kotlin  (0) 2018.10.06
[BOJ] 1068번 트리 byKotlin  (0) 2018.10.02
BOJ 2789번 유학금지 by Kotlin  (0) 2018.07.18

BOJ(백준) 1068번 트리



문제 : 입력으로 주어진 트리에서 한 노드를 지웠을 때, 남은 트리에서 리프 노드 개수 구하기.


설명: 

 루트부터 자식들을 BFS로 계속 찾아가는 방법으로 풀었다. 각 노드에 방문시 확인해주면서 leaf 노드의 개수를 추가한다.

 확인하는 것 = 1. 만약 자식의 개수가 1개고, 그 자식이 삭제한 노드이면 . Leaf 노드 이므로 결과값에 +1

                    2. 만약 자식이 없으면 Leaf 노드이므로 결과값에 +1  

 

 

 주어진 입력에서 각 노드의 부모를 배열로 입력받는다.  ex) -1 0 0 1 1   --> 0번 노드는 root이고,  1번,2번 노드의 부모는 0번 노드이고, 3,4번 노드의 부모는 1번 노드이다. 

=> 이 입력을 바꾸어서, parent node 번호에 자식 node 번호를 저장한다.

  adj[노드 번호] 에는 해당 노드의 자식 번호들이 저장되어있다.



(문제 바로가기 : boj.kr/1068)



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
 
fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine()!!.toInt()
    val adj = Array(n) { LinkedList<Int>() }
    var root = 0
    var tmp = 0
    val st = StringTokenizer(br.readLine()!!)
    while (st.hasMoreTokens()) {
        val parent = st.nextToken().toInt()
        if (parent != -1) {
            adj[parent].add(tmp++)
        } else root = tmp++
    }
    val remove = br.readLine()!!.toInt()
 
    val q = LinkedList<Int>()
    var res = 0
    q.add(root)
    while (!q.isEmpty()) {
        val here = q.poll()
        if (here == remove) continue
        if (adj[here].size == 0 || (adj[here].size == 1 && adj[here][0] == remove)) {
            res++
            continue
        }
        for (next in adj[here]) {
            if (next != remove) {
                q.add(next)
            }
        }
    }
    println(res)
}
cs


저작자표시 비영리 변경금지

'BOJ(백준)' 카테고리의 다른 글

[BOJ] 2170번 선 긋기 by Kotlin  (0) 2018.11.13
[BOJ] 1017번 소수 쌍 by Kotlin  (0) 2018.10.07
[BOJ] 1671번 상어의 저녁식사 by Kotlin  (0) 2018.10.06
[BOJ] 1021번 회전하는 큐 - by Kotlin  (0) 2018.10.02
BOJ 2789번 유학금지 by Kotlin  (0) 2018.07.18

+ Recent posts

티스토리툴바