Jenikeju

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

내가 푼 풀이

- 1번을 통해 접근할 수 있는 모든 노드의 갯수를 구한다.

- 단순히 1번과 연결되어 있는지 판단만 하기 때문에, 순서는 상관이 없으므로 BFS DFS 둘 다 사용 가능하다.

- 연결된 리스트들을 모두 탐색후, 방문했던 노드들의 개수 -1 출력 (1이 포함되어 있기 때문)

import Foundation

let comCount = Int(readLine()!)!
let netCount = Int(readLine()!)!
var graph = [Int: [Int]]()

// 인접리스트 저장
for i in 0..<netCount {
    let input = readLine()!.split(separator: " ").map{ Int($0)! }
    if graph[input[0]] == nil {
        graph[input[0]] = [input[1]]
    } else {
        graph[input[0]]!.append(input[1])
    }
    if graph[input[1]] == nil {
        graph[input[1]] = [input[0]]
    } else {
        graph[input[1]]!.append(input[0])
    }
}

// BFS
// 인접한 노드를 방문하는것에 중점이기에, 순서는 상관이없어서 DFS를 사용해도 된다.
var visitedQueue = [Int]()
var needVisitQueue = [1]

while !needVisitQueue.isEmpty {
    var node = needVisitQueue.removeFirst()
    if visitedQueue.contains(node) { continue }
    visitedQueue.append(node)
    
    needVisitQueue += graph[node]!
}
print(visitedQueue.count - 1)

내가 푼 풀이

-  0번째열에 있는 지점에서 C-1열까지 연결이 된다면, 횟수를 올려준다.

- 연결이 되었다면, 연결된 지점들은 다른 문자열로 변환한다. (파이프는 겹칠수없기때문에)

- 만약 연결할 수 없더라도 이전에 연결했던 파이프라인들은 다른문자열로 변환한다. 다른지점에서 출발을해도, 연결될 수 없기때문이다.

- 위의 조건대로 코드로 구현해본다.

재귀적호출을 이용해 한 지점에서 연결할 수 있는 모든 위치들을 불러온다.

그렇게 마지막지점까지 도달한다면, 연결이된것이므로 연결된 위치들을 다른 문자열로 바꿔준다.

import Foundation

var inputs = readLine()!.split(separator: " ").map{ Int($0)! }
var arr = [[String]]()
var result = 0
var isFind = false

// 배열 입력
for i in 0..<inputs[0] {
    var a = readLine()!.map{String($0)}
    arr.append(a)
}

// 현재 위치에서 오른쪽대각위, 오른쪽, 오른쪽대각아래 순으로 검사한다.
// 마지막열에 도달했다면, 경로를 찾은것,
// 경로를 찾았다면 이전의 재귀함수들을 모두 실행중단해준다.
func find(x: Int, y: Int) {
    arr[x][y] = "O"
    if y == inputs[1] - 1 {
        isFind = true
        result += 1
        return
    }
    if x > 0 && arr[x-1][y+1] == "." {
        if isFind { return }
            find(x: x-1, y: y+1)
    }
    if arr[x][y+1] == "." {
        if isFind { return }
        find(x: x, y: y+1)
    }
    if x < inputs[0] - 1 && arr[x+1][y+1] == "." {
        if isFind { return }
        find(x: x+1, y: y+1)
    }
    
}
for i in 0..<inputs[0] {
    isFind = false
    find(x: i, y: 0)
}
print(result)

ㅈ 

내가 푼 풀이

- (N K)는 (a+b)^N의 k번째 항의 이항계수이다.

- N = 0이면 (a+b)^0 = 1

- N = 1이면 (a+b)^1 = a + b 이므로 이항계수는 1 1 이된다.

위 이항계수는 다음과 같이 성립한다.

dp[n][k] = dp[n-1][k-1] + dp[n-1][k]가 된다.

점화식을 토대로 코드로 구현하면 다음과 같다.

import Foundation
// dp생성
var inputs = readLine()!.split(separator: " ").map{ Int($0)! }
var dp = Array(repeating: Array(repeating: 0, count: inputs[0]+1), count: inputs[0]+1)

// k = 0 , k = n 인경우 1 저장
// k는 n보다 클 수 없다.
// 나머지 경우 점화식에따라 입력
for i in 0..<dp.count {
    for j in 0..<dp.count {
        if j > i {
            continue
        }
        if j == 0 || i == j {
            dp[i][j] = 1
        } else {
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % 10007
        }
    }
}
print(dp[inputs[0]][inputs[1]])

내가 푼 풀이

- 주어진 배열 N x M에서 (1, 1)에서 (N, M)까지 이동하는 최소 칸 수를 구하면 된다.

- dp로 풀 수 있을꺼같지만, BFS를 이용해서 풀었다.

- 주어진 인덱스와 인접한 4방향 위치 중에 1인값들을 저장했다.

- maze[[Int]: [[Int]]] = key는 x, y값이고 value는 인접한 위치 중 이동할 수 있는 위치의 인덱스 x, y 들로 구성되었다.

- x =1, y = 1 부터 시작해서 인접한 위치를 탐색하며, 그 위치 중 이미 방문했던 곳이 있다면, 그곳까지의 칸수 + 1을 하는 방법을 사용했다.

위에 예시로 주어진 배열을 이용해서 예로들어본다.

네 방향으로 인접한 위치 중 방문할 수 있는 위치인지 파악하기 위해 (N+2) * (M+2) 크기로 만들어준다.

그리고 해당 위치까지 이동했을 때, 이동한 칸수의 최솟값을 저장할 배열 하나를 같은 크기로 만들어주고, [1,1]에 1을 저장.

인접한 인덱스 중 방문할 수 있는 위치를 리스트로 만든다.

[1,1]은 [2,1]과 인접하고, [2,1]은 [1,1]과 [3,1]이 인접한다.

[1,1]: [2,1]

[2,1]: [1,1], [3,1]

BFS를 이용해 1,1 이 인접한 위치로 이동하며, 이동한 위치 [2,1]에서 인접한 위치 [1,1], [3,1] 중 이미 방문했던 위치가 있다면,

그 위치 [1,1] 값 +1을 해준다.

그러면 결과배열에 다음과 같이 저장된다.

위 방법을 통해 방문할 수 있는 모든 위치를 지나게 된다면, 결과 배열은 다음과 같이 저장된다.

마지막 m, n 위치의 값을 출력하면 된다.

해당 알고리즘을 코드로 구현하면 다음과 같다.

import Foundation

// 결과배열 result
// 인접된 인덱스리스트 maze
var index = readLine()!.split(separator: " ").map{ Int($0)! }
var arr = [Array(repeating: 0, count: index[1]+2)]
var maze = [[Int]: [[Int]]]()
var result = Array(repeating: Array(repeating: 0, count: index[1]+2), count: index[0]+2)
result[1][1] = 1

// (N+2) * (M+2) 크기의 배열 만들기
for i in 0..<index[0] {
    var nums = Array(readLine()!).map{ Int(String($0))!}
    arr.append([0] + nums + [0])
}
arr.append(Array(repeating: 0, count: index[1]+2))

// 인접리스트 maze 입력하기
for i in 1...index[0] {
    for j in 1...index[1] {
        if arr[i][j] == 1 {
            if arr[i-1][j] == 1 {
                if maze[[i,j]] == nil {
                    maze[[i,j]] = [[i-1,j]]
                } else {
                    maze[[i,j]]!.append([i-1,j])
                }
            }
            if arr[i][j-1] == 1 {
                if maze[[i,j]] == nil {
                    maze[[i,j]] = [[i,j-1]]
                } else {
                    maze[[i,j]]!.append([i,j-1])
                }
            }
            if arr[i+1][j] == 1 {
                if maze[[i,j]] == nil {
                    maze[[i,j]] = [[i+1,j]]
                } else {
                    maze[[i,j]]!.append([i+1,j])
                }
            }
            if arr[i][j+1] == 1 {
                if maze[[i,j]] == nil {
                    maze[[i,j]] = [[i,j+1]]
                } else {
                    maze[[i,j]]!.append([i,j+1])
                }
            }
        }
    }
}

// 방문한 위치 배열
// 방문해야 할 위치 배열
var visitedQueue = [[Int]]()
var needVisitQueue = [[1,1]]

// BFS
while !needVisitQueue.isEmpty {
    var node = needVisitQueue.removeFirst()
    
    if visitedQueue.contains(node) { continue }
    visitedQueue.append(node)
    needVisitQueue += maze[node]!
    // 해당 위치가 시작지점이면 패스
    // 해당위치 이전의 방문한 위치가 있다면 그 위치의값 + 1
    if node == [1,1] {
        continue
    } else {
        for i in maze[node]! {
            if visitedQueue.contains(i) {
                result[node[0]][node[1]] += result[i[0]][i[1]] + 1
                break
            }
        }
    }
}

print(result[index[0]][index[1]])

내가 푼 풀이

- 그리디의 단골문제로 높은단위의 동전으로 최대한 거슬러주면된다.

- 무작정 거슬러주면 주어진 거스름돈으로 줄 수 없으므로, 5원을 받은 돈을 나눈 몫부터 1씩 차감하면서 나머지 2원으로 거슬러준다.

- 거스르지못하면 -1 출력

import Foundation

var money = Int(readLine()!)!
var result = 0
var max = money / 5
var isDone = false

// 5원으로 최대한 걸러줬을때, 2원으로 거를 수 있다면 동전갯수 출력
// 거스르지 못하면 5원의 갯수 1씩차감
// 5원의 갯수가 0개인데 2원으로 거스르지 못하면 -1 출력
while max >= 0 {
    var m = money - (max * 5)
    if m % 2 == 0 {
        result = max + (m / 2)
        isDone = true
        break
    } else {
        max -= 1
    }
}

if isDone {
    print(result)
} else {
    print(-1)
}

내가 푼 풀이

- 연산의 최대횟수가 100,000이고, 배열의 크기가 최대 1024이므로 단순히 주어진 연산의 범위만큼 반복문을 돌리면,

최악의 경우 연산횟수가 100,000 * 1024 * 1024나 되므로, 계산된값을 저장하고 이용하기로 했다.

- 주어진 (N+1) x (N+1) 크기의 배열 dp를 선언한다.

- 행과 열이 인덱스가 0인경우 0을 넣어준다.

- dp[i][j] = 1행 1열부터 i행 j열까지 더한 범위의 값이라고 정의하자.

- (x1, y1) , (x2, y2) 가 주어졌을때,

- 예시로 4 x 4 배열이 주어졌을때, (2, 2) (3,4)의 범위는 아래와같다.

이 범위의 연산결과는 아래처럼 나타낼 수 있다.

위의 큰 배열에서 

위 두가지 범위를 빼준 후

이 범위를 더해주면 된다.

이를  0,0부터 i,j까지의 연산범위합이 들어간 dp[i][j]를 이용하면 아래와 같이 나타낼 수 있다.

- dp[3][4] - dp[1][4] - dp[4][1] + dp[1][1] 

위 공식을 이용해서 연산결과들을 출력한다.

(x1, y1) , (x2, y2) 의 범위가 주어졌을때, 해당 범위의 연산결과는

dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1] 

import Foundation

var counts = readLine()!.split(separator: " ").map{ Int($0)! }
var arr = [Array(repeating: 0, count: counts[0] + 1)]
var dp = Array(repeating: Array(repeating: 0, count: counts[0] + 1), count: counts[0] + 1)
// 주어진 n x n 배열 저장
// (n+1) x (n+1) 크기로 저장하고, 행렬의 인덱스가 0이면 0 저장
for i in 0..<counts[0] {
    arr.append([0] + readLine()!.split(separator: " ").map{ Int($0)! })
}

// dp[i][j] = 0,0 부터 i,j까지 모두 합한 결과를 저장
for i in 1..<dp.count {
    for j in 1..<dp.count {
        dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + arr[i][j]
    }
}

// 해당 범위만큼의 연산결과 출력
for i in 0..<counts[1] {
    var inputs = readLine()!.split(separator: " ").map{ Int($0)! }
    let x1 = inputs[0]
    let y1 = inputs[1]
    let x2 = inputs[2]
    let y2 = inputs[3]

    print(dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1])
}

내가 푼 풀이

- DFS 와 BFS 알고리즘으로 푼다.

- 정점이 여러개면, 접점 번호가 작은 것부터 먼저 방문한다

- DFS는 Dictionary에서 마지막원소를 빼므로 내림차순, BFS는 첫 번째 원소를 빼므로 오름차순으로 정렬한다.

import Foundation

let inputs = readLine()!.split(separator: " ").map{ Int($0)! }
var dict = [Int: [Int]]()

// 그래프 입력
for i in 0..<inputs[1] {
    let input = readLine()!.split(separator: " ").map{ Int($0)! }
    if dict[input[0]] == nil {
        dict[input[0]] = [input[1]]
    } else if !dict[input[0]]!.contains(input[1]) {
        dict[input[0]]!.append(input[1])
    }
    if dict[input[1]] == nil {
        dict[input[1]] = [input[0]]
    } else if !dict[input[1]]!.contains(input[0]) {
        dict[input[1]]!.append(input[0])
    }
}

var visitedQueue = [Int]()
var visitedQueue2 = [Int]()
var needVisitStack = [inputs[2]]

// DFS
// 인접한 접점번호가 작은순이므로, 접점번호가 저장된배열을 내림차순으로 정렬한다.
while !needVisitStack.isEmpty {
    let node = needVisitStack.removeLast()
    if visitedQueue.contains(node) { continue }
    
    visitedQueue.append(node)
    needVisitStack += dict[node]?.sorted{ $0 > $1 } ?? []
}

// BFS
// 인접한 접점번호가 작은순이므로, 접점번호가 저장된배열을 오름차순으로 정렬한다.
needVisitStack = [inputs[2]]
while !needVisitStack.isEmpty {
    let node = needVisitStack.removeFirst()
    if visitedQueue2.contains(node) { continue }
    
    visitedQueue2.append(node)
    needVisitStack += dict[node]?.sorted{ $0 < $1 } ?? []
}

print(visitedQueue.map{ String($0)}.joined(separator: " "))
print(visitedQueue2.map{ String($0)}.joined(separator: " "))

내가 푼 풀이

- 주어진 레벨을 배열로 만들었을때 원소가 중복되지 않으며, 오름차순으로 만들어야 한다.

- 주어진 배열의 인덱스순으로 난이도가 오름차순이므로, 정렬하지 않고 마지막 어려운 레벨부터 점수를 수정한다.

- 현재 레벨이 이전 레벨보다 점수가 작거나 같으면 이전레벨의 점수를 현재레벨의 점수 - 1로 바꾸고,

- 이전레벨의 점수 - 현재레벨의 점수 + 1 해준다.

- 이를 배열의 첫 번째 원소까지 모두 해주면, 원소가 중복되지 않는 오름차순으로 만들어진다.

import Foundation

let count = Int(readLine()!)!
var arr = [Int]()
var result = 0

// 레벨 점수 입력
for i in 0..<count {
    arr.append(Int(readLine()!)!)
}

// 마지막레벨부터 검사한다.
// 현재레벨이 이전레벨보다 점수가 낮거나 같으면 수정
// 이전레벨의 점수 = 현재레벨의 점수 - 1
// 점수감소횟수 = 이전레벨의 점수 - 현재레벨의 점수 + 1
for i in (1..<arr.count).reversed() {
    if arr[i] <= arr[i-1] {
        result += arr[i-1] - arr[i] + 1
        arr[i-1] = arr[i] - 1
    }
}

print(result)