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

 

2232번: 지뢰

일직선상에 N개의 지뢰가 같은 간격으로 매설되어 있다. 각각의 지뢰는 충격 강도 Pi가 있어서, Pi를 초과하는 힘을 가하면 Pi만큼의 힘을 발휘하며 터지게 된다. 어떤 지뢰가 터지게 되면, 그 지

www.acmicpc.net

너비우선탐색으로 접근한 문제다.

 

풀이

입력받은 지뢰의 충격이 큰 순서부터 터트리면서 너비우선탐색을 수행한다. 이때 터트리는 지뢰의 번호를 입력받은 뒤 오름차순으로 정렬하여 출력하면 된다.

 

정답 코드

import Foundation
let n = Int(readLine()!)!
var visited = Array(repeating: false, count: n)
var arr = [(Int,Int)]()
var map = [Int]()
var ans = [Int]()
func bfs(from a:Int){
ans.append(a+1)
let nx = [-1,1]
var q = [a]
var idx = 0
while idx<q.count{
let curr = q[idx]
let value = map[curr]
for i in 0..<2{
let next = nx[i]+curr
if next<0 || next>=n{ continue }
if !visited[next] && map[next]<value{
visited[next] = true
q.append(next)
}
}
idx += 1
}
}
for i in 0..<n{
let power = Int(readLine()!)!
arr.append((i,power))
map.append(power)
}
arr.sort(by: {$0.1<$1.1})
for _ in 0..<n{
let curr = arr.removeLast()
let idx = curr.0
if !visited[idx]{
visited[idx] = true
bfs(from: idx)
}
}
for ans in ans.sorted(by: <){
print(ans)
}
view raw 2232.swift hosted with ❤ by GitHub

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

[2350] 대운하  (0) 2022.12.25
[15991] 1, 2, 3 더하기 6  (0) 2022.12.24
[2143] 두 배열의 합  (0) 2022.12.20
[2610] 회의준비  (0) 2022.12.19
[14594] 동방 프로젝트 (Small)  (0) 2022.12.18

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

 

2143번: 두 배열의 합

첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그

www.acmicpc.net

누적합과 이분 탐색을 통해 접근하였다.

 

풀이

두 배열의 누적합을 통해 부 배열을 생성, 두 개의 부 배열 중 하나의 부 배열을 오름차순 정렬한 뒤 이분 탐색을 수행, (T - 다른 부배열의 원소) 값을 찾아낸다면 해당 값의 개수만큼 정답을 추가하여 마지막에 출력하면 된다.

 

정답 코드

import Foundation
let T = Int(readLine()!)!
var n = Int(readLine()!)!
var a = [0]
for number in readLine()!.split(separator: " ").map({Int($0)!}){
a.append(a.last!+number)
}
var m = Int(readLine()!)!
var b = [0]
for number in readLine()!.split(separator: " ").map({Int($0)!}){
b.append(b.last!+number)
}
var tempA = [Int]()
var tempB = [Int:Int]()
for i in 0..<n{
for k in i+1..<n+1{
tempA.append(a[k]-a[i])
}
}
for i in 0..<m{
for k in i+1..<m+1{
let num = b[k]-b[i]
if tempB[num] == nil{
tempB[num] = 1
}else{
tempB[num]! += 1
}
}
}
let numbers = tempB.sorted(by: { $0.key < $1.key})
var ans = 0
for i in 0..<tempA.count{
var lead = 0
var trail = numbers.count-1
while lead <= trail{
let mid = (lead+trail)/2
if numbers[mid].key == T-tempA[i]{
ans += numbers[mid].value
break
}else if numbers[mid].key > T-tempA[i]{
trail = mid-1
}else{
lead = mid+1
}
}
}
print(ans)
view raw 2143.swift hosted with ❤ by GitHub

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

[15991] 1, 2, 3 더하기 6  (0) 2022.12.24
[2232] 지뢰  (0) 2022.12.21
[2610] 회의준비  (0) 2022.12.19
[14594] 동방 프로젝트 (Small)  (0) 2022.12.18
[16168] 퍼레이드  (0) 2022.12.16

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

 

2610번: 회의준비

첫째 중에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이

www.acmicpc.net

유니온 파인드와 플로이드 와샬로 접근 가능한 문제다. 문제 속 함정에 걸려 시간을 많이 소비한 문제다. 문제를 꼼꼼히 읽도록 하자.

 

풀이

입력받은 간선 정보를 통해 유니온 파인드를 통해 컴포넌트를 구분, 2차원 배열을 통해 각 노드 간의 거리를 갱신한다. 입력이 완료되면 플로이드 와샬 알고리즘을 통해 각 노드 간의 최소거리를 구한다. 

 

유니온 파인드를 통해 알게 된 루트 노드를 입력하면 해당 컴포넌트의 최소 의사전달시간을 구하면 된다. 여기서 주의할 점은 문제에 주어진 "위원회에서 모든 참석자들의 의사전달시간 중 최댓값이 최소가 되도록"이라는 부분이다. 해당 부분이 무엇인지 잘 생각하고 접근해야 한다.

 

다음으로 주의할 점은 "각 위원회의 대표 번호를 작은 수부터 차례로 한 줄에 하나씩 출력한다." 부분이다. 처음에 아무 생각 없이 0부터 n까지 순번으로 탐색하면 당연하게 순번대로 출력이 될 거라고 생각했으나, 낮은 순번의 루트를 호출하여 더 높은 번호가 대표가 되는 경우가 존재한다. 결국 대표의 번호를 따로 담아 정렬한 뒤에 출력해주었다.

 

정답 코드

import Foundation
let INF = Int.max
let n = Int(readLine()!)!
let m = Int(readLine()!)!
var arr = Array(repeating: -1, count: n)
var info = [(a:Int,b:Int)]()
var map = Array(repeating: Array(repeating: INF, count: n), count: n)
func root(of a:Int)->Int{
if arr[a]<0 { return a }
arr[a] = root(of: arr[a])
return arr[a]
}
func union(a:Int, b:Int){
let rootA = root(of: a)
let rootB = root(of: b)
if rootA == rootB {return}
arr[rootB] = rootA
}
func dist(from a:Int) -> Int{
var visited = Array(repeating: false, count: n)
var q = [a]
var idx = 0
var myMin = INF
var ans = a
visited[a] = true
while idx<q.count{
let curr = q[idx]
var time = 0
for i in 0..<n{
if map[curr][i]==INF{continue}
time = max(time, map[curr][i])
if !visited[i]{
visited[i] = true
q.append(i)
}
}
if myMin>time{
myMin = time
ans = curr
}
idx += 1
}
return ans+1
}
for _ in 0..<m{
let line = readLine()!.split(separator: " ").map{Int($0)!-1}
let u = line[0]
let v = line[1]
union(a: u, b: v)
map[u][v] = 1
map[v][u] = 1
}
for p in 0..<n{
for i in 0..<n{
for k in 0..<n{
if map[i][p]==INF || map[p][k]==INF || i==k{continue}
map[i][k] = min(map[i][k], map[i][p]+map[p][k])
}
}
}
var ans = [Int]()
var cnt = 0
for i in 0..<n{
if arr[i] < 0{
cnt += 1
ans.append(dist(from: i))
}
}
print(cnt)
for ans in ans.sorted(by: <){
print(ans)
}
view raw 2610.swift hosted with ❤ by GitHub

조건에 대한 이해력이 너무나도 중요한 문제였다.

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

[2232] 지뢰  (0) 2022.12.21
[2143] 두 배열의 합  (0) 2022.12.20
[14594] 동방 프로젝트 (Small)  (0) 2022.12.18
[16168] 퍼레이드  (0) 2022.12.16
[13905] 세부  (0) 2022.12.14

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

 

14594번: 동방 프로젝트 (Small)

첫 번째 행동으로 1번과 2번 방이 합쳐져 (1, 2), (3), (4), (5) 상태가 된다. 이후 두 번째 행동으로 2, 3, 4번 방이 합쳐져 (1, 2, 3, 4), (5)의 상태가 된다. 따라서 남아있는 동방의 수는 2가 된다.

www.acmicpc.net

유니온 파인드 문제다. 문제는 같지만 입력 범위가 넓은 14595 문제를 풀다가 시간 초과하여 범위가 좁은 해당 문제부터 풀어보았다.

 

풀이

들어온 입력에 맞게 범위 단위로 유니온을 해준뒤 루트의 개수를 세면 된다. x < y 라는 조건이 있으니, x의 루트만 찾아낸 후 x+1 ~ y 범위까지 전부 x의 루트로 변경하면 된다.

 

정답 코드

import Foundation
let n = Int(readLine()!)!
let m = Int(readLine()!)!
var rooms = Array(repeating: -1, count: n)
func root(of n:Int)->Int{
if rooms[n]<0 {return n}
rooms[n] = root(of: rooms[n])
return rooms[n]
}
func union(a:Int, b:Int){
let rootA = root(of: a)
for i in a+1...b{
rooms[i] = rootA
}
}
for _ in 0..<m{
let uv = readLine()!.split(separator: " ").map{Int($0)!-1}
let u = uv[0]
let v = uv[1]
union(a: u, b: v)
}
var cnt = 0
for room in rooms{
if room<0{cnt+=1}
}
print(cnt)
view raw 14594.swift hosted with ❤ by GitHub

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

[2143] 두 배열의 합  (0) 2022.12.20
[2610] 회의준비  (0) 2022.12.19
[16168] 퍼레이드  (0) 2022.12.16
[13905] 세부  (0) 2022.12.14
[16724] 피리 부는 사나이  (0) 2022.12.13

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

 

16168번: 퍼레이드

첫 번째 줄에 지점의 개수 V, 연결 구간의 개수 E가 주어진다. (1 ≤ V ≤ E ≤ 3000) 이후 E개의 줄에 걸쳐 각 연결 구간이 연결하는 두 지점의 번호 Va, Vb가 공백을 사이에 두고 주어진다. (1 ≤ Va,

www.acmicpc.net

유니온 파인드 문제다. 오일러 경로를 이용해야 한다.

 

풀이

문제에서 주어지는 것은 모든 간선을 한 번에 이용하면서 모든 노드의 순회가 가능하냐는 것이다. 즉 주어진 도형을 한 손 그리기가 가능하냐로 생각이 가능하다. 

이에 관한 공식이 있는지 찾아보았는데, '오일러 경로'에 대한 자료를 찾을 수 있었다. 각 노드의 진입, 진출 차수의 합이 짝수이면 한붓그리기가 가능하며, 예외적으로 차수가 홀수인 것이 2개라면 한붓 그리기가 가능하다고 한다.

차수가 홀수인 것이 0개 또는 2개라면 한붓그리기가 가능하다

따라서 문제에서 요구하는 것을 요약하자면, 모든 정점이 하나의 컴포넌트인지, 그렇다면 각 노드의 차수가 홀수인 경우가 0 또는 2라면 해당 그래프는 퍼레이드가 가능한 그래프인 것으로 출력하면 된다.

 

정답 코드

import Foundation
let ve = readLine()!.split(separator: " ").map{Int($0)!}
let v = ve[0]
let e = ve[1]
var arr = Array(repeating: -1, count: v)
var degrees = Array(repeating: 0, count: v)
func root(of n:Int)->Int{
if arr[n]<0 {return n}
arr[n] = root(of: arr[n])
return arr[n]
}
func union(a:Int, b:Int){
let rootA = root(of: a)
let rootB = root(of: b)
if rootA == rootB{ return }
arr[rootB] = rootA
}
for _ in 0..<e{
let uv = readLine()!.split(separator: " ").map{Int($0)!-1}
let u = uv[0]
let v = uv[1]
degrees[u] += 1
degrees[v] += 1
union(a: u, b: v)
}
var flag = false
var cnt = 0
var degree = 0
for i in 0..<v{
if degrees[i]%2 == 1{ degree+=1 }
if arr[i]<0{ cnt += 1 }
}
if cnt==1 && (degree == 0 || degree == 2) { flag = true }
print(flag ? "YES":"NO")
view raw 16168.swift hosted with ❤ by GitHub

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

[2610] 회의준비  (0) 2022.12.19
[14594] 동방 프로젝트 (Small)  (0) 2022.12.18
[13905] 세부  (0) 2022.12.14
[16724] 피리 부는 사나이  (0) 2022.12.13
[20955] 민서의 응급 수술  (0) 2022.12.12

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

 

13905번: 세부

첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄

www.acmicpc.net

최소 스패닝 트리 문제다. 단 여기서 간선의 비용이 최대가 되게 구하면 된다. 주의할 점은 숭이가 위치한 곳과 혜빈이가 위치한 곳이 다리로 연결된다는 보장이 없다는 것을 숙지하고 풀어야 한다. 이것 때문에 오답 판정을 받았다.

 

풀이

입력되는 간선의 가중치, 즉 무게가 높은 순으로 간선의 정보를 정렬한 뒤, 가중치가 높은 순서로 유니온을 수행한다. 유니온을 수행할 때마다 들고 갈 수 있는 빼빼로의 무게를 작은 값으로 갱신, 마지막으로 숭이와 혜빈이의 위치가 같은 컴포넌트에 속해있는지 확인한 후, 같은 컴포넌트가 아니라면, 빼빼로를 전달할 수 없는 것이므로 0을 출력, 같은 컴포넌트가 맞다면 갱신해온 무게 값을 출력하면 된다.

 

정답 코드

import Foundation
let nm = readLine()!.split(separator: " ").map{Int($0)!}
let se = readLine()!.split(separator: " ").map{Int($0)!-1}
let n = nm[0]
let m = nm[1]
let s = se[0]
let e = se[1]
var edges = [(u:Int,v:Int,cost:Int)]()
var house = Array(repeating: -1, count: n)
var cost = 1000001
func root(of n:Int) -> Int{
if house[n] < 0 {return n}
house[n] = root(of: house[n])
return house[n]
}
func union(a:Int, b:Int, c:Int){
let rootA = root(of: a)
let rootB = root(of: b)
if rootA == rootB{ return }
house[rootB] = rootA
cost = min(cost, c)
}
for _ in 0..<m{
let line = readLine()!.split(separator: " ").map{Int($0)!}
let edge = (line[0]-1,line[1]-1,line[2])
edges.append(edge)
}
edges.sort(by: { $0.cost > $1.cost })
for edge in edges {
if root(of: s) == root(of: e){ break }
union(a: edge.u, b: edge.v, c: edge.cost)
}
print(root(of: s)==root(of: e) ? cost:0)
view raw 13905.swift hosted with ❤ by GitHub

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

[14594] 동방 프로젝트 (Small)  (0) 2022.12.18
[16168] 퍼레이드  (0) 2022.12.16
[16724] 피리 부는 사나이  (0) 2022.12.13
[20955] 민서의 응급 수술  (0) 2022.12.12
[10216] Count Circle Groups  (0) 2022.12.11

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

 

16724번: 피리 부는 사나이

첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주

www.acmicpc.net

유니온 파인드 문제다. 추가적으로 그래프 탐색을 통해 접근했다.

 

풀이

문제에 "지도 밖으로 나가는 방향은 주어지지 않는다"는 입력 조건이 있다. 그 얘기는 주어지는 좌표 어느 부분이던 탐색 시 무조건 사이클이 일어난다는 것이고, 문제의 답은 사이클이 일어나는 영역에 하나씩 "safe zone"을 설치하면 된다는 이야기. 요약하자면 깊이 우선 탐색을 통해 유니온파인드를 통해 컴포넌트의 개수를 반환하면 되는 것이다.

예제의 입력을 기준으로 사이클이 일어나는 영역을 색으로 표시해 놓았다. 두 개의 구역으로 나뉘며, 구역 하나당 하나의 "safe zone"을 설치하면 최소 개수를 구할 수 있다.

고민했던 점은 유니온을 할 때, 어떻게 구별하느냐인데, 이전에 풀었던 문제에서 2차원 배열을 번호로 매겨서 1차원 배열에 대입하여 풀었던 기억이 나서 그 부분을 사용했다. 즉 깊이 우선 탐색을 하면서 해당 위치의 번호와 다음 위치의 번호를 유니온, 루트가 같다면 종료. 모든 좌표에 대해서 깊이 우선 탐색을 수행한 뒤, 컴포넌트의 개수를 출력해주면 된다.

 

정답 코드

import Foundation
let nm = readLine()!.split(separator: " ").map{Int($0)!}
let n = nm[0]
let m = nm[1]
var map = Array(repeating: Array(repeating: "", count: m), count: n)
var arr = Array(repeating: -1, count: n*m)
var safeZone = 0
func root(of n:Int)->Int{
if arr[n]<0 { return n}
arr[n] = root(of: arr[n])
return arr[n]
}
func union(a:Int, b:Int){
let rootA = root(of: a)
let rootB = root(of: b)
if rootA <= rootB{
arr[rootB] = rootA
}else{
arr[rootA] = rootB
}
}
func dfs(num:Int){
let curr = root(of: num)
let x = num/m
let y = num%m
var nx = x
var ny = y
switch map[x][y]{
case "U":
nx -= 1
case "D":
nx += 1
case "L":
ny -= 1
case "R":
ny += 1
default:
break
}
let next = root(of: nx*m+ny)
if curr == next{
return
}
union(a: curr, b: next)
dfs(num: next)
}
for i in 0..<n{
let line = readLine()!.map{String($0)}
map[i] = line
}
for i in 0..<n*m{
dfs(num: i)
}
for i in 0..<n*m{
if arr[i]<0{
safeZone += 1
}
}
print(safeZone)
view raw 16724.swift hosted with ❤ by GitHub

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

[16168] 퍼레이드  (0) 2022.12.16
[13905] 세부  (0) 2022.12.14
[20955] 민서의 응급 수술  (0) 2022.12.12
[10216] Count Circle Groups  (0) 2022.12.11
[17250] 은하철도  (0) 2022.12.10

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

 

20955번: 민서의 응급 수술

민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서

www.acmicpc.net

유니온 파인드 문제다. 문제의 내용만 잘 이해한다면 쉽게 풀 수 있는 문제다.

 

풀이

문제에서 요구하는 것은 모든 뉴럴들을 사이클이 없는 하나의 그래프로 만들려면 몇 번의 연산이 필요한지 구하는 것이다. 역으로 생각하면 주어진 뉴럴들의 연결 상태에서 사이클이 몇 번 일어나는지, 그리고 컴포넌트의 개수를 합산하여 출력하면 된다. 

사이클이 일어난다는 것은 주어진 두 뉴럴의 루트가 같다는 것. 즉 유니온이 일어날 때, 두 노드의 루트를 확인하는데, 이때 루트가 같다면 연결을 끊어내는 작업을 해야 하므로 연산 횟수 1 증가.

최종 컴포넌트의 상태를 확인할 때, 컴포넌트가 2개 이상이라면 하나로 합치는 연산을 수행하므로 (총 컴포넌트 개수 - 1) 횟수를 추가하여 출력하면 된다.

 

정답 코드

import Foundation
let nm = readLine()!.split(separator: " ").map{Int($0)!}
let n = nm[0]
let m = nm[1]
var arr = Array(repeating: -1, count: n)
var cnt = 0
func root(of a:Int) -> Int{
if arr[a]<0 {return a}
arr[a] = root(of: arr[a])
return arr[a]
}
func union(a:Int, b:Int){
let rootA = root(of: a)
let rootB = root(of: b)
if rootA == rootB {
cnt += 1
return
}
arr[rootB] = rootA
}
for _ in 0..<m{
let info = readLine()!.split(separator: " ").map{Int($0)!-1}
union(a: info[0], b: info[1])
}
for i in 0..<n{
if arr[i]<0 { cnt += 1 }
}
print(cnt-1)
view raw 20955.swift hosted with ❤ by GitHub

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

[13905] 세부  (0) 2022.12.14
[16724] 피리 부는 사나이  (0) 2022.12.13
[10216] Count Circle Groups  (0) 2022.12.11
[17250] 은하철도  (0) 2022.12.10
[18116] 로봇 조립  (0) 2022.12.09

+ Recent posts

티스토리툴바