고도고도
🍎🍏
고도고도
전체 방문자
13,424
오늘
31
어제
64
  • 분류 전체보기 (170)
    • 🔨 프로젝트 (0)
      • TP 1 (0)
      • WhiteHCCTV (0)
      • FootPrint (0)
    • 💻 개발 (61)
      • iOS (28)
      • Android (6)
      • Kotlin (4)
      • Flutter (9)
      • Node.js (5)
      • Architecture (1)
      • 오늘의 삽질 (7)
      • 에러와의 동침 (1)
    • ✏️ 알고리즘 (6)
      • Graph (6)
      • String (0)
      • Sort (0)
    • ✍️ 코테 준비 (44)
      • Math (1)
      • Implementation (3)
      • String (3)
      • Brute Force (5)
      • Back Tracking (7)
      • Greedy (0)
      • Dynamic Programming (13)
      • Binary Search (1)
      • DFS, BFS (5)
      • Shortest Path (2)
      • Two Pointer (4)
      • MST (0)
    • 📚 CS (6)
      • Operating System (6)
    • ⛹️ 라이프 (53)
      • 2020 겨울방학 모칵코(팀) (13)
      • 2020 겨울방학 모각코(개인) (13)
      • 2021 여름방학 모칵코(팀) (8)
      • 2021 여름방학 모각코(개인) (7)
      • 코딩 테스트 (1)
      • 회고 (10)

블로그 메뉴

  • 홈
  • 깃허브
  • 링크드인

공지사항

인기 글

  • [NCSOFT] 2022 엔씨소프트 썸머 인턴 후기 - 1⋯
    2022.08.10
    [NCSOFT] 2022 엔씨소프트 썸머 인턴 후기 - 1⋯
  • [Flutter] SingleChildScrollView,⋯
    2021.08.18
    [Flutter] SingleChildScrollView,⋯
  • [iOS / SwiftUI] MapKit, 실시간으로 도로⋯
    2022.12.20
    [iOS / SwiftUI] MapKit, 실시간으로 도로⋯
  • [Android] 백그라운드에서 소켓 통신으로 이벤트 수신⋯
    2022.06.08
    [Android] 백그라운드에서 소켓 통신으로 이벤트 수신⋯
  • [iOS / SwiftUI] OnAppear, OnDisa⋯
    2022.12.01
    [iOS / SwiftUI] OnAppear, OnDisa⋯

최근 댓글

  • https://developer.apple.com/docu⋯
    고도고도
  • 게시글 잘 보았습니다. 혹시 주소에서 구를 가지고 오시는⋯
    나그네
  • 혹시 댓글이 안보이는데 .. y2e010924@naver.⋯
    eun
  • 글 솜씨가 뛰어나시네요! 좋은 글 잘 보고 갑니다 다음에도⋯
    alpha-traveler
  • NC......가슴이...웅장해집니다.......🤯
    이상한핑구 🐧

최근 글

  • [Architecture] MVVM + Clean Arch⋯
    2023.01.07
    [Architecture] MVVM + Clean Arch⋯
  • [iOS / SwiftUI] MapKit, 실시간으로 도로⋯
    2022.12.20
    [iOS / SwiftUI] MapKit, 실시간으로 도로⋯
  • [iOS / SwiftUI] OnAppear, OnDisa⋯
    2022.12.01
    [iOS / SwiftUI] OnAppear, OnDisa⋯
  • [에러와의 동침] 22년 11월 4주차
    2022.11.28
    [에러와의 동침] 22년 11월 4주차
  • [iOS / SwiftUI] 스크롤, 무한으로 즐겨요~ (⋯
    2022.11.28
    [iOS / SwiftUI] 스크롤, 무한으로 즐겨요~ (⋯

티스토리

hELLO · Designed By 정상우.
고도고도

🍎🍏

[백트래킹 / Kotlin] BOJ 14889 - 스타트와 링크
✍️ 코테 준비/Back Tracking

[백트래킹 / Kotlin] BOJ 14889 - 스타트와 링크

2022. 4. 10. 12:21

문제

풀이 언어

Kotlin

코드

import java.lang.Integer.min
import java.util.*
import kotlin.math.abs
import kotlin.system.exitProcess

lateinit var board: Array<Array<Int>>
lateinit var visited: Array<Int>
var min_value = Int.MAX_VALUE
var n = 0

fun main() = with(Scanner(System.`in`)) {
    n = nextInt()
    board = Array(n) { Array(n) { nextInt() } }
    visited = Array(n) { 0 }

    search(0, 0)
    println(min_value)
}

fun search(index: Int, depth: Int) {
    if (depth == n / 2) {
        calculate()
        return
    }

    for (i in index until n) {
        if (visited[i] == 0) {
            visited[i] = 1
            search(i + 1, depth + 1)
            visited[i] = 0
        }
    }
}

fun calculate() {
    var start = 0
    var link = 0

    for (i in 0 until n - 1) {
        for (j in i until n) {
            if (visited[i] == 1 && visited[j] == 1) {
                start += board[i][j]
                start += board[j][i]
            } else if (visited[i] == 0 && visited[j] == 0) {
                link += board[i][j]
                link += board[j][i]
            }
        }
    }

    val score = abs(start - link)

    if (score == 0) {
        println(score)
        exitProcess(0)
    }

    min_value = min(score, min_value)
}

풀이 방법

개인적으로 백트래킹 어떻게 적용할지를 발견하지 못해서 앞서 작성한 골드 문제보다 어려웠다. 우선 2개의 팀 (스타트팀, 링크팀) 으로 나누어야 한다. 방문 지점을 스타트팀 으로 두고 방문하지 않는 지점을 링크팀 으로 두고 문제를 해결했다.

 

1. 2개의 팀으로 나누므로 depth == n / 2 인 경우에 점수 계산

fun search(index: Int, depth: Int) {
    if (depth == n / 2) {
        calculate()
        return
    }

    for (i in index until n) {
        if (visited[i] == 0) {
            visited[i] = 1
            search(i + 1, depth + 1)
            visited[i] = 0
        }
    }
}

 

2. 방문한 지점을 스타트팀으로, 방문하지 않은 지점을 링크팀으로 두고 점수 계산

    for (i in 0 until n - 1) {
        for (j in i until n) {
            if (visited[i] == 1 && visited[j] == 1) {
                start += board[i][j]
                start += board[j][i]
            } else if (visited[i] == 0 && visited[j] == 0) {
                link += board[i][j]
                link += board[j][i]
            }
        }
    }

    val score = abs(start - link)
    min_value = min(score, min_value)

 

3. 점수의 차이가 0이면 최소값이므로 DFS를 진행하지 않고 종료

    if (score == 0) {
        println(score)
        exitProcess(0)
    }

결과

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

'✍️ 코테 준비 > Back Tracking' 카테고리의 다른 글

[백트래킹 / Kotlin] BOJ 1759 - 암호 만들기  (0) 2022.04.10
[백트래킹 / Kotlin] BOJ 1987 - 알파벳  (0) 2022.04.10
[백트래킹 / Kotlin] BOJ 14888 - 연산자 끼워넣기  (0) 2022.03.31
[백트래킹 / Kotlin] BOJ 2580 - 스도쿠  (0) 2022.03.30
[백트래킹 / Kotlin] BOJ 9663 - N Queen  (0) 2022.03.29
    '✍️ 코테 준비/Back Tracking' 카테고리의 다른 글
    • [백트래킹 / Kotlin] BOJ 1759 - 암호 만들기
    • [백트래킹 / Kotlin] BOJ 1987 - 알파벳
    • [백트래킹 / Kotlin] BOJ 14888 - 연산자 끼워넣기
    • [백트래킹 / Kotlin] BOJ 2580 - 스도쿠
    고도고도
    고도고도
    iOS 꿀잼
    댓글쓰기
    [백트래킹 / Kotlin] BOJ 1759 - 암호 만들기
    이전 글
    [백트래킹 / Kotlin] BOJ 1759 - 암호 만들기

    티스토리툴바