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

 

17471번: 게리맨더링

선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다.

www.acmicpc.net

조합을 통한 완전탐색 + 유니온파인드로 접근하였다.

접근 방법

입력으로 주어지는 구역의 최대개수는 10이다. 따라서 각 구역이 두 가지 선거구로 선택되는 경우의 수를 계산하면 2^10 즉 1024의 경우의 수가 발생. 이후 각 조건에서 유니온 파인드를 수행한다.

유니온 파인드에서 두 노드가 결합되는 조건은 서로 인접하며 정해진 선거구가 같은 경우만 결합하는 것으로 하였다. 마지막으로 컴포넌트의 수가 2인 경우만 각 선거구의 인구수를 확인하여 정답을 반영하면 된다.

정답 코드

import Foundation
let N = Int(readLine()!)!
var population = readLine()!.split(separator: " ").map{Int($0)!}
var total = population.reduce(0, +)
var edges = [(u:Int, v:Int)]()
var ans = Int.max
for u in 0..<N{
let info = readLine()!.split(separator: " ").map{Int($0)!}
let n = info[0]
if n == 0{ continue }
for i in 1...n{ edges.append((u,info[i]-1))}
}
var list = [[String]]()
func btk(team:[String]){
var team = team
if team.count == N{
list.append(team)
return
}
team.append("R")
btk(team: team)
team.removeLast()
team.append("B")
btk(team: team)
}
btk(team: [])
for team in list{
var arr = population.map{-1*$0}
var cnt = N
var red = 0
var blue = 0
for i in 0..<N{
if team[i] == "R"{
red += population[i]
}else{
blue += population[i]
}
}
func root(of node:Int) -> Int{
if arr[node] < 0{ return node }
arr[node] = root(of: arr[node])
return arr[node]
}
func union(a:Int, b:Int){
let A = root(of: a)
let B = root(of: b)
if team[a] != team[b] { return }
if A==B { return }
arr[A] += arr[B]
arr[B] = A
cnt -= 1
}
for edge in edges {
union(a: edge.u, b: edge.v)
}
if cnt == 2{
ans = min(ans,abs(red-blue))
}
}
print(ans==Int.max ? -1:ans)
view raw 17471.swift hosted with ❤ by GitHub

'Problem Solving > BOJ' 카테고리의 다른 글

[13397] 구간 나누기 2  (0) 2024.02.28
[8983] 사냥꾼  (0) 2024.02.19
[1700] 멀티탭 스케줄링  (0) 2024.01.30
[23286] 허들 넘기  (0) 2024.01.18
[5582] 공통 부분 문자열  (0) 2024.01.12

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

 

1700번: 멀티탭 스케줄링

기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전

www.acmicpc.net

풀이 방법

핵심은 콘센트가 가득 차있을 경우 어떤 전기용품을 뺄지를 결정하는 것이다.

정답은 앞으로 사용하지 않을 기기 혹은 앞으로 사용할 예정인 기기로 가득 차있는 경우라면 그중에서 가장 나중에 사용할 기기를 빼면 된다.

 

질문게시판에 좋은 예제가 있어 해당 예제로 설명하면 다음과 같이 동작한다.

3 10
1 2 3 4 4 5 2 1 1 4

 

각 전기용품별 사용될 순서의 시기를 스택형태로 저장한다. 맨 아래는 콘센트의 상태.
콘센트가 가득 찰때 까지 전기용품을 할당한다. 초기의 1,2,3은 바로 할당된다. 할당됨과 동시에 각 전기용품에 해당하는 사용횟수는 차감된다.
4번 전기용품이 할당될 때, 콘센트에 할당 된 3번은 더이상 사용되지 않으므로 3번을 뺀고 4번을 할당하게 된다.
콘센트에 이미 할당된 기기가 사용될 경우 횟수를 차감한다.
5번이 할당될 때, 1,2,4의 할당 순서를 확인, 스택의 top이 가장 큰 번호를 가진 4번 전기용품이 콘센트에서 분리된다.
마지막으로 4번이 할당될때는 1,2,5 전부 더이상 사용되지않으므로 셋중 하나를 분리하면 된다.

정답 코드

import Foundation
let (N,K) = [readLine()!.split(separator: " ").map{Int($0)!}].map{($0[0], $0[1])}[0]
var arr = readLine()!.split(separator: " ").map{Int($0)!-1}
var order = Array(repeating: [Int](), count: K)
var outlet = Set<Int>()
var ans = 0
for i in (0..<K).reversed(){
let num = arr[i]
order[num].append(i)
}
for num in arr{
if outlet.contains(num){
order[num].removeLast()
continue
}else if outlet.count < N{
outlet.insert(num)
order[num].removeLast()
}else{
var target = -1
var idx = -1
for k in outlet{
if order[k].isEmpty{
idx = k
break
}
if order[k].last! > target{
target = order[k].last!
idx = k
}
}
outlet.remove(idx)
outlet.insert(num)
order[num].removeLast()
ans += 1
}
}
print(ans)
view raw 1700.swift hosted with ❤ by GitHub

'Problem Solving > BOJ' 카테고리의 다른 글

[8983] 사냥꾼  (0) 2024.02.19
[17471] 게리멘더링  (0) 2024.02.06
[23286] 허들 넘기  (0) 2024.01.18
[5582] 공통 부분 문자열  (0) 2024.01.12
[17396] 백도어  (0) 2023.12.27

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

 

23286번: 허들 넘기

첫째 줄에 세 정수 N, M, T가 주어진다. 다음 M개의 줄에 그래프 간선의 정보 u, v, h가 주어지고, u에서 v로 가는 간선이 있고, 높이가 h인 허들이 간선 중간에 놓여 있다는 의미이다. 마지막 T개의

www.acmicpc.net

최단거리 탐색 알고리즘으로 접근한 문제다. 

풀이

특정 정점에서 다른 정점까지의 최단거리를 계산하는 다익스트라 알고리즘을 사용했다. 이때 핵심은 주어지는 T의 범위가 40,000이라는 점이다. 즉 매 연습마다 40,000번의 그래프 탐색이 일어난다면 시간초과로 이어진다.

 

정점의 개수 N이 최대 300이며 간선의 최대 개수는 25,000인 점을 고려한다면 이전에 사용했던 정보가 중복으로 요구된다는 합리적인 결론에 도달한다.

 

따라서 다익스트라 알고리즘을 구현한 뒤 결과 값을 저장할 수 있는 <시작점, 각 정점까지의 최단거리> 형태의 딕셔너리를 생성하여 이전에 요구한 적 없는 시작점이 주어진다면 다익스트라 알고리즘을 통해 해당 결과를 저장한다. 반대로 이전에 요구한 적이 있던 시작점이라면 해당 시작점으로부터의 최단거리 정보는 이미 저장되어 있으므로 바로 출력이 가능하다.

 

즉 매 횟수마다 최단거리를 계산할 경우 O(4,000 * 25,000)의 시간복잡도로 인해 시간초과가 일어나겠지만, 모든 정점에서 다익스트라 알고리즘을 미리 수행한 결과를 이용한다면 O(300 * 25,000)의 시간복잡도로 시간 단축이 가능하다는 얘기다.

정답 코드

import Foundation
let (N,M,T) = [readLine()!.split(separator: " ").map{Int($0)!}].map{($0[0], $0[1], $0[2])}[0]
var map = Array(repeating: [(node:Int, cost:Int)](), count:N)
for _ in 0..<M{
let (u,v,h) = [readLine()!.split(separator: " ").map{Int($0)!}].map{($0[0]-1, $0[1]-1, $0[2])}[0]
map[u].append((v,h))
}
func dijk(from root:Int) -> [Int]{
var minCost = Array(repeating: -1, count: N)
var q = [(node:Int, cost:Int)]()
var dq = q
minCost[root] = 0
q.append((root,0))
while !q.isEmpty{
dq = q.reversed()
q.removeAll()
for _ in 0..<dq.count{
let curr = dq.removeLast()
if minCost[curr.node] < curr.cost{ continue }
for next in map[curr.node]{
let newCost = max(curr.cost, next.cost)
if minCost[next.node]<0 || minCost[next.node]>newCost{
minCost[next.node] = newCost
q.append((next.node, newCost))
}
}
}
q.sort(by: {$0.cost < $1.cost})
}
return minCost
}
var ans = Dictionary<Int,[Int]>()
for _ in 0..<T{
let (S,E) = [readLine()!.split(separator: " ").map{Int($0)!-1}].map{($0[0], $0[1])}[0]
if ans[S] == nil{
ans[S] = dijk(from: S)
}
print(ans[S]![E])
}
view raw 23286.swift hosted with ❤ by GitHub

'Problem Solving > BOJ' 카테고리의 다른 글

[17471] 게리멘더링  (0) 2024.02.06
[1700] 멀티탭 스케줄링  (0) 2024.01.30
[5582] 공통 부분 문자열  (0) 2024.01.12
[17396] 백도어  (0) 2023.12.27
[23040] 누텔라 트리 (Easy)  (0) 2023.11.10

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

 

5582번: 공통 부분 문자열

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들

www.acmicpc.net

처음엔 길이가 짧은 문자열에서 부분문자열을 뽑아낸 뒤 길이가 긴 문자열에 포함되는지 여부를 통해서 접근했지만 당연하게도 시간초과.

동적계획법 태그를 보고서 접근법을 생각해 봤지만 결국 풀이를 찾아봤다. 점화식부터 말하면 다음과 같다.

dp[i][k] = dp[i-1][k-1] + 1

여기서 2차원 배열 dp는 해당 위치의 문자로 끝나는 공통 부분 문자열의 길이를 뜻한다.

풀이

문자열 A = "AACD"와 문자열 B = "SSAB"를 기준으로 설명하면 다음과 같이 작동한다.

문자열 A의 길이 N, 문자열 B의 길이 M 일 때, (N+1)*(M+1) 크기의 2차원배열 dp를 생성. 0으로 초기화한다.

1부터 N, 1부터 B까지 2중 반복문을 탐색하면서 점화식을 통해 계산한 값 중 최댓값이 정답이다.

 

 

두 문자열의 i번째와 k번째 문자가 일치했다는 것은 두 문자열의 i-1번째와 k-1번째 문자로 끝나는 공통 부분 문자열에 현재 문자를 이어 붙여 한 글자 더 긴 공통부분 문자열을 만들 수 있다는 뜻이 된다.

 

즉 O(N*M) 의 시간복잡도를 통해서 해당 문제를 해결할 수 있다.

정답코드

import Foundation
let A = readLine()!.map{String($0)}
let B = readLine()!.map{String($0)}
var dp = Array(repeating: Array(repeating: 0, count: A.count+1), count: B.count+1)
var ans = 0
for i in 1...B.count{
for k in 1...A.count{
if B[i-1]==A[k-1]{
dp[i][k] = dp[i-1][k-1]+1
}
ans = max(ans,dp[i][k])
}
}
print(ans)
view raw 5582.swift hosted with ❤ by GitHub

'Problem Solving > BOJ' 카테고리의 다른 글

[1700] 멀티탭 스케줄링  (0) 2024.01.30
[23286] 허들 넘기  (0) 2024.01.18
[17396] 백도어  (0) 2023.12.27
[23040] 누텔라 트리 (Easy)  (0) 2023.11.10
[20530] 양분  (1) 2023.11.04

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

 

17396번: 백도어

첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는

www.acmicpc.net

최단거리 탐색 문제다. 다익스트라 알고리즘으로 접근했다.

풀이

접근 가능한 정점과 N-1번 정점을 이어주는 간선들만 저장했다.

 

swift에는 다른 언어들과 달리 Heap이 구현되어있지 않아서 일반적인 경우에는 일반 큐를 사용하여 매 순환마다 정렬 작업을 하여 탐색하였는데 이번 문제는 간선정보가 최대 300,000개가 주어지므로 Heap 구현이 필요했다.

 

글 읽기 - 다익스트라 시간초과 질문드립니다

댓글을 작성하려면 로그인해야 합니다.

www.acmicpc.net

그런데 마주한 시간초과. 질문게시판을 찾아보니 다익스트라 알고리즘의 원리를 잘 고민하면 우선순위 큐를 더 빠르게 탐색이 가능하다고 한다. 

 

우선 다익스트라 알고리즘은 비용이 낮은 순으로 정렬된 우선순위 큐를 탐색하여 매 순간 각 정점으로의 최소비용을 갱신하게 된다.

즉, [현재 정점의 최소비용 + 현재 정점에서 다음 정점까지의 비용] 계산을 통해 다음 정점의 최단거리 정보를 갱신하는데, 이때 우선순위 큐에서 꺼낸  현재 정점의 정보가 최소 비용이 아니라면 결국 다음 정점까지의 정보를 탐색할 필요가 없다는 얘기다.

 

따라서 매 탐색마다 최단거리 정보를 담고 있는 cost[curr]와 우선순위 큐에 담겨있는 curr.cost 와의 비교를 통해서 최단거리보다 큰 비용이라면 continue를 통해 시간단축이 가능하다.

정답 코드

import Foundation
//by rhyno
public struct Heap<T> {
var nodes: [T] = []
let comparer: (T,T) -> Bool
var isEmpty: Bool {
return nodes.isEmpty
}
init(comparer: @escaping (T,T) -> Bool) {
self.comparer = comparer
}
func peek() -> T? {
return nodes.first
}
mutating func insert(_ element: T) {
var index = nodes.count
nodes.append(element)
while index > 0, !comparer(nodes[index],nodes[(index-1)/2]) {
nodes.swapAt(index, (index-1)/2)
index = (index-1)/2
}
}
mutating func delete() -> T? {
guard !nodes.isEmpty else {
return nil
}
if nodes.count == 1 {
return nodes.removeFirst()
}
let result = nodes.first
nodes.swapAt(0, nodes.count-1)
_ = nodes.popLast()
var index = 0
while index < nodes.count {
let left = index * 2 + 1
let right = left + 1
if right < nodes.count {
if comparer(nodes[left], nodes[right]),
!comparer(nodes[right], nodes[index]) {
nodes.swapAt(right, index)
index = right
} else if !comparer(nodes[left], nodes[index]){
nodes.swapAt(left, index)
index = left
} else {
break
}
} else if left < nodes.count {
if !comparer(nodes[left], nodes[index]) {
nodes.swapAt(left, index)
index = left
} else {
break
}
} else {
break
}
}
return result
}
}
extension Heap where T: Comparable {
init() {
self.init(comparer: <)
}
}
let (N,M) = [readLine()!.split(separator: " ").map{Int($0)!}].map{($0[0], $0[1])}[0]
var node = readLine()!.split(separator: " ").map{$0=="0" ? true:false}
var map = Array(repeating: [(node:Int, cost:Int)](), count: N)
var visited = Array(repeating: false, count: N)
var q = Heap<(node:Int, cost:Int)>(comparer: {$0.cost > $1.cost})
var cost = Array(repeating: -1, count: N)
for _ in 0..<M{
let (u,v,cost) = [readLine()!.split(separator: " ").map{Int($0)!}].map{($0[0], $0[1], $0[2])}[0]
if (u==N-1 && node[v]) || (v==N-1 && node[u]) || (node[u] && node[v]){
map[u].append((v,cost))
map[v].append((u,cost))
}
}
cost[0] = 0
q.insert((0,0))
while !q.isEmpty{
let curr = q.delete()!
if cost[curr.node] < curr.cost { continue }
for next in map[curr.node]{
let newCost = cost[curr.node] + next.cost
if cost[next.node]<0 || cost[next.node]>newCost{
cost[next.node] = newCost
q.insert((next.node, newCost))
}
}
}
print(cost[N-1])
view raw 17396.swift hosted with ❤ by GitHub

'Problem Solving > BOJ' 카테고리의 다른 글

[23286] 허들 넘기  (0) 2024.01.18
[5582] 공통 부분 문자열  (0) 2024.01.12
[23040] 누텔라 트리 (Easy)  (0) 2023.11.10
[20530] 양분  (1) 2023.11.04
[15559] 내 선물을 받아줘  (0) 2023.10.31

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

 

23040번: 누텔라 트리 (Easy)

첫째 줄에 트리의 정점의 개수 $N$이 주어진다. ($2 \le N \le 100\,000$) 이후 $(N-1)$개 줄에 걸쳐 각 간선이 잇는 두 정점의 번호 $u_i$, $v_i$가 공백을 사이에 두고 주어진다. ($1 \le u_i \le N$, $1 \le v_i \le N$,

www.acmicpc.net

유니온파인드와 그래프탐색으로 접근했다.

풀이

모든 정점을 방문하게 된다면 시간초과가 일어난다.

 

 

예제를 보면 3~1, 3~5, 3~4, 3~2, 6~4, 6~2 총 6개의 구간이 정답이다.

검은색 정점을 시작으로 빨간색 정점으로만 이어지는 경로의 개수. 즉 우리는 연속되는 빨간색 정점을 컴포넌트로 묶어 개수를 미리 저장해 놓으면 보다 빠르게 탐색이 가능해진다.

 

따라서 인접한 빨간색 정점끼리는 유니온을 통해 하나의 컴포넌트로 묶어내어 개수를 저장하고, 컴포넌트에 인접한 검은색 정점의 개수를 파악하면 해당 컴포넌트에서 발생되는 누텔라 트리의 개수를 구할 수 있게 된다. 

 

해당 과정은 bfs를 통해 O(N)만에 정답을 구할 수 있다.

정답 코드

import Foundation
// by rhyno
final class FileIO {
private let buffer:[UInt8]
private var index: Int = 0
init(fileHandle: FileHandle = FileHandle.standardInput) {
buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
}
@inline(__always) private func read() -> UInt8 {
defer { index += 1 }
return buffer[index]
}
@inline(__always) func readInt() -> Int {
var sum = 0
var now = read()
var isPositive = true
while now == 10
|| now == 32 { now = read() } // 공백과 줄바꿈 무시
if now == 45 { isPositive.toggle(); now = read() } // 음수 처리
while now >= 48, now <= 57 {
sum = sum * 10 + Int(now-48)
now = read()
}
return sum * (isPositive ? 1:-1)
}
@inline(__always) func readString() -> String {
var now = read()
while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
let beginIndex = index-1
while now != 10,
now != 32,
now != 0 { now = read() }
return String(bytes: Array(buffer[beginIndex..<(index-1)]), encoding: .ascii)!
}
}
let file = FileIO()
let N = file.readInt()
var ans = 0
var arr = Array(repeating: -1, count: N)
var map = Array(repeating: [Int](), count: N)
var visited = Array(repeating: false, count: N)
func root(of node:Int) -> Int{
if arr[node] < 0 { return node }
arr[node] = root(of: arr[node])
return arr[node]
}
func union(a:Int, b:Int) {
let A = root(of: a)
let B = root(of: b)
if A==B {return}
arr[A] += arr[B]
arr[B] = A
}
for _ in 0..<N-1{
let u = file.readInt()-1
let v = file.readInt()-1
map[u].append(v)
map[v].append(u)
}
var colorOf = file.readString().map{String($0)}
func bfs(from vertex:Int) -> Int{
var q = [vertex]
var cnt = 0
var idx = 0
while idx < q.count{
let curr = q[idx]
for next in map[curr]{
if colorOf[next] == "R" && !visited[next]{
visited[next] = true
union(a: curr, b: next)
q.append(next)
}else if colorOf[next] == "B"{
cnt += 1
}
}
idx += 1
}
return cnt * abs(arr[root(of: vertex)])
}
for i in 0..<N{
if colorOf[i] == "R" && !visited[i]{
visited[i] = true
ans += bfs(from: i)
}
}
print(ans)
view raw 23040.swift hosted with ❤ by GitHub

'Problem Solving > BOJ' 카테고리의 다른 글

[5582] 공통 부분 문자열  (0) 2024.01.12
[17396] 백도어  (0) 2023.12.27
[20530] 양분  (1) 2023.11.04
[15559] 내 선물을 받아줘  (0) 2023.10.31
[1765] 닭싸움 팀 정하기  (0) 2023.10.30

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

 

20530번: 양분

첫째 줄에 두 자연수 $N$, $Q$가 주어진다. 주어지는 그래프의 정점과 간선의 개수가 $N$개이며 쿼리가 $Q$개 주어진다는 것을 의미한다. 둘째 줄부터 $N$개의 줄에는 $i$번 간선이 연결하는 두 정점

www.acmicpc.net

그래프 탐색과 유니온파인드로 접근했다.

풀이

정점 N개와 간선 N개를 가진 트리는 한 개의 사이클을 가지고 있는 트리이다. 따라서 정점 u에서 v로 가는 경로가 사이클을 거쳐가게 된다면 경로는 2개가 되고, 경로에 사이클이 없다면 경로는 1개가 되는 것이다.

 

따라서 사이클에 속해있는 정점을 파악한 뒤 유니온 파인드를 수행하다. 연결하려 하는 두 정점의 경로가 사이클에 속한 경로라면, 정점을 연결하지 않고 넘어간 뒤, 쿼리가 주어질 때, 두 정점의 부모가 같다면 1 아니면 2를 출력하면 정답이다.

 

 

주어진 예제를 통해 보면 정점 1 - 2 - 3으로 사이클이 이루어진다. 따라서 정점 1, 2, 3 사이의 간선을 없애고 쿼리에서 서로 다른 컴포넌트의 경로를 물어보면 해당 경로는 사이클을 통한 경로가 있다는 뜻이므로 2를 출력, 같은 컴포넌트 내의 경로를 물어보면 1을 출력하면 된다.

 

사이클 검출은 진입차수가 1인 정점부터 너비 우선 탐색을 수행하여 찾아내었다. 

정답 코드

import Foundation
//by rhyno
final class FileIO {
private let buffer:[UInt8]
private var index: Int = 0
init(fileHandle: FileHandle = FileHandle.standardInput) {
buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
}
@inline(__always) private func read() -> UInt8 {
defer { index += 1 }
return buffer[index]
}
@inline(__always) func readInt() -> Int {
var sum = 0
var now = read()
var isPositive = true
while now == 10
|| now == 32 { now = read() } // 공백과 줄바꿈 무시
if now == 45 { isPositive.toggle(); now = read() } // 음수 처리
while now >= 48, now <= 57 {
sum = sum * 10 + Int(now-48)
now = read()
}
return sum * (isPositive ? 1:-1)
}
}
let file = FileIO()
let N = file.readInt()
let Q = file.readInt()
var arr = Array(repeating: -1, count: N)
var edges = [(u:Int, v:Int)]()
var indegree = Array(repeating: 0, count: N)
var map = Array(repeating: [Int](), count: N)
func root(of node:Int) -> Int{
if arr[node]<0 { return node }
arr[node] = root(of: arr[node])
return arr[node]
}
func union(a:Int, b:Int){
let A = root(of: a)
let B = root(of: b)
if A==B { return }
if indegree[a]>1 && indegree[b]>1 { return }
arr[B]=A
}
func findLoop(){
var visited = Array(repeating: false, count: N)
var q = [Int]()
var idx = 0
for i in 0..<N{
if indegree[i] == 1{
visited[i] = true
q.append(i)
}
}
while idx<q.count{
let curr = q[idx]
for next in map[curr]{
indegree[next] -= 1
if !visited[next] && indegree[next]==1{
visited[next] = true
q.append(next)
}
}
idx += 1
}
}
for _ in 0..<N{
let u = file.readInt()-1
let v = file.readInt()-1
edges.append((u,v))
indegree[u] += 1
indegree[v] += 1
map[u].append(v)
map[v].append(u)
}
findLoop()
for edge in edges{
union(a: edge.u, b: edge.v)
}
for _ in 0..<Q{
let u = file.readInt()-1
let v = file.readInt()-1
print(root(of: u) == root(of: v) ? 1:2)
}
view raw 20530.swift hosted with ❤ by GitHub

'Problem Solving > BOJ' 카테고리의 다른 글

[17396] 백도어  (0) 2023.12.27
[23040] 누텔라 트리 (Easy)  (0) 2023.11.10
[15559] 내 선물을 받아줘  (0) 2023.10.31
[1765] 닭싸움 팀 정하기  (0) 2023.10.30
[23324] 어려운 모든 정점 쌍 최단 거리  (0) 2023.10.25

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

 

15559번: 내 선물을 받아줘

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000, 1 < N×M ≤ 1,000,000) 둘째 줄부터 N개의 줄에는 구사과가 있는 곳의 지도가 주어진다.  지도에 쓰여 있는대로 이동했을

www.acmicpc.net

유니오 파인드와 그래프 탐색으로 접근했다.

풀이

2차원 지도를 1차원 배열로 매핑한 뒤 지도에 적힌 움직임 대로 그래프 탐색을 수행한다.

탐색을 수행하면서 현재 위치와 다음으로 이동할 위치의 번호끼리 합병해 주면 된다.

컴포넌트의 개수를 출력해 주면 정답이다.

 

단, 중복 방문을 막는 과정에서 실수하여 WA를 받았다.

반례는 문제에 주어진 예제를 보고 생각해 냈다.

 

3 4

SWWW

SEEN

EEEN

 

방문했던 위치여도 아직 방문하지 않은 곳에서 진입이 가능하기에 방문했던 위치도 무조건 유니온 동작을 수행해야 한다.

정답 코드

import Foundation
let (N,M) = [readLine()!.split(separator: " ").map{Int($0)!}].map{($0[0], $0[1])}[0]
var visited = Array(repeating: false, count: N*M)
var map = [[String]]()
var arr = Array(repeating: -1, count: N*M)
var ans = N*M
var DIR = Dictionary<String,(dx:Int, dy:Int)>()
DIR["N"] = (-1,0)
DIR["S"] = (1,0)
DIR["W"] = (0,-1)
DIR["E"] = (0,1)
func root(of node:Int) -> Int{
if arr[node]<0 { return node }
arr[node] = root(of: arr[node])
return arr[node]
}
func union(a:Int, b:Int){
let A = root(of: a)
let B = root(of: b)
if A==B { return }
arr[B] = A
ans -= 1
}
func dfs(from curr:Int){
let x = curr/M
let y = curr%M
let dir = map[x][y]
let nx = x+DIR[dir]!.dx
let ny = y+DIR[dir]!.dy
let next = (nx*M)+ny
union(a: curr, b: next)
if !visited[next] {
visited[next] = true
dfs(from: next)
}
}
for _ in 0..<N{
let info = readLine()!.map{String($0)}
map.append(info)
}
for i in 0..<N{
for k in 0..<M{
let curr = (i*M)+k
if !visited[curr]{
visited[curr] = true
dfs(from: curr)
}
}
}
print(ans)
view raw 15559.swift hosted with ❤ by GitHub

'Problem Solving > BOJ' 카테고리의 다른 글

[23040] 누텔라 트리 (Easy)  (0) 2023.11.10
[20530] 양분  (1) 2023.11.04
[1765] 닭싸움 팀 정하기  (0) 2023.10.30
[23324] 어려운 모든 정점 쌍 최단 거리  (0) 2023.10.25
[23743] 방탈출  (0) 2023.10.01

+ Recent posts

티스토리툴바