Dev.YoungKyu
YoungKyu's Devlog
전체 방문자
오늘
어제
  • 분류 전체보기 N
    • 부스트캠프
    • iOS N
    • visionOS
    • Backend
    • 알고리즘
    • CS
    • Git
    • Python
    • 끄적끄적

블로그 메뉴

  • 홈
  • 🌝 티스토리 홈
  • ⭐️ 깃허브
  • 태그

공지사항

인기 글

최근 댓글

최근 글

태그

  • 티스토리챌린지
  • MVC
  • Git
  • swift
  • jekyll
  • Animation
  • alamofire
  • 부스트캠프
  • Python
  • Concurrency
  • ios
  • Optional
  • image
  • Swift5.7
  • constraint
  • 백준
  • 모듈화
  • 알고리즘
  • 소프트웨어 테스트
  • 소프트웨어 공학
  • CS
  • ImageResource
  • AVAudioSession
  • if let
  • guard
  • 소프트웨어공학
  • 오블완
  • boj
  • AutoLayout
  • SwiftUI

티스토리

hELLO · Designed By 정상우.
Dev.YoungKyu
[백준] BOJ-14889 스타트와 링크
알고리즘

[백준] BOJ-14889 스타트와 링크

2022. 11. 27. 23:06

문제

누르면 문제 페이지로 이동합니다.

 

문제 풀이

알고리즘 스터디 1주차 문제로, DFS, 백트래킹 알고리즘으로 접근하며 문제풀이를 시작했다. 

백트래킹은 "DFS를 기반으로 하며, 어느 정도의 Depth 에 도달하면 탐색을 중단 하는 알고리즘" 정도로 이해하고 접근했다.

 

n이 무조건 짝수로 제공되고, 절반 씩 팀을 나누기 때문에 dfs로 순차 탐색을 진행하다가 n / 2 일 경우 탐색을 중단하고

팀원을 구성하도록 했다.

 

두 팀간의 능력치 차이가 가장 적은 경우의 능력치 차이를 출력하는 문제이기에

result 변수의 초기값을 Int.max 로 설정해둔 후, 

min() 과 abs() 함수를 사용해 두 팀 간의 능력치 차이를 구하고 result 와 비교해 더 적은 값으로 업데이트 하도록 했다.

 

import Foundation

let n = Int(readLine()!)!
var arr = Array(repeating: Array(repeating: 0, count: n), count: n)
var visited = [Bool](repeating: false, count: n)
var result = Int.max

for i in 0..<n {
    arr[i] = readLine()!.split(separator: " ").map { Int($0)! }
}

func dfs(depth: Int, start: Int) {
    // depth 가 n/2 라는 뜻은 이미 한 팀 구성이 완료 됐다는 뜻
    // 그래서 depth/2 가 되면, 팀구성못한애들을(false) team2에 넣어줌!!
    if depth == n/2 {
        var team1 = 0
        var team2 = 0
        
        for i in 0..<n {
            for j in 0..<n {
                if !visited[i] && !visited[j] { // 방문안한 애들은 team2
                    team2 += arr[i][j]
                }
                if visited[i] && visited[j] { // 방문한 애들은 team1
                    team1 += arr[i][j]  
                }
            }
        }
 
        // 팀 간의 능력치 차이가 더 적으면 기존 result 와 업데이트
        result = min(result, abs(team1 - team2))
        return
    }
    
    // 탐색
    for i in start..<n {
        if !visited[i] {
            visited[i] = true
            dfs(depth: depth + 1, start: i)
            visited[i] = false
        }
    }
}

dfs(depth: 0, start: 0)
print(result)

 

후기

DFS가 알고리즘 문제에서 활용도가 높은 것 같다. 필요할 때 자유자재로  활용 있게 연습해야겠다.

저작자표시 (새창열림)

'알고리즘' 카테고리의 다른 글

[알고리즘] 구간 합, 누적 합(Prefix Sum)  (0) 2024.03.11
[프로그래머스] PRG-JadenCase 문자열 만들기  (0) 2022.09.19
[백준 BOJ] BOJ -2309 일곱 난쟁이  (0) 2022.09.18
[백준 BOJ] BOJ-1018 체스판 다시 칠하기  (0) 2022.09.18
[백준 BOJ] BOJ-8393 합  (0) 2022.09.18
    '알고리즘' 카테고리의 다른 글
    • [알고리즘] 구간 합, 누적 합(Prefix Sum)
    • [프로그래머스] PRG-JadenCase 문자열 만들기
    • [백준 BOJ] BOJ -2309 일곱 난쟁이
    • [백준 BOJ] BOJ-1018 체스판 다시 칠하기
    Dev.YoungKyu
    Dev.YoungKyu
    iOS를 공부하고 있습니다

    티스토리툴바