프로그래머스의 AI가 추천해준 탐색, 자료구조 문제이다.
프로그래머스-전력망을 둘로 나누기
트리(Tree) 형태란?
우선 문제 분석할 때, 확인해야하는 부분은 '하나의 트리'형태로 연결되어 있다고한다. 트리(Tree)는 그래프(Graph)의 일종이라고 볼 수 있는데 간단하게 트리의 특징을 정리하고 가자.
트리의 특징
- 계층 구조를 가지고 있다.
노드들이 부모-자식 관계로 이루어진 계층적인 구조를 가지는데 이때, 자식 노드는 하나의 부모 노드를 가지게된다. (부모 노드는 여러 자식 노드를 가질 수 있다.) - 루트 노드와 리프 노드.
트리에서 가장 맨 위에 있는 노드를 루트 노드, 반대로 가장 맨 밑에 있는 노드를 리프 노드라고 한다.
Tree Image
위의 설명을 보여주는 이미지의 예시는 아래와 같다.
부모는 여러개의 자식을 가지고, 자식은 하나의 부모를 가지게 된다.
그리고 가장 위와 가장 밑의 노드를 루트와 리프라고 부른다.
D, H, I를 서브트리라고 하는데, 이는 트리 내에서 어떤 노드와 그 자손들로 이루어진 것을 서브트리라고 한다.
간단하게 Graph와 Tree를 비교하게 되면 왼쪽에 있는 Graph는 D와 E로 이어져 트리구조가 아니게 된다.
문제풀이
1. 루트 만들기
문제에서는 송전탑의 개수(n)와 송전탑이 어디와 연결되어 있는지를 파악할 수 있는 전선 정보(wires)를 제공한다.
그러면 우선 적으로 Tree 구조를 만들어 보는 것이다.
// tree에서 특정 송전탑과 이어져 있는 송전탑 목록 표시
var tree: [Int: [Int]] = [:] // [송전탑A: [송전탑A와 연결된 송전탑들]]
// Tree 만들기
for wire in wires {
// wire에서 첫번째 값에 해당되는 내용이 있는가?
if tree[wire[0]] != nil {
tree[wire[0]]?.append(wire[1])
} else {
tree[wire[0]] = [wire[1]]
}
// wire에서 두번째 값에 해당되는 내용이 있는가?
if tree[wire[1]] != nil {
tree[wire[1]]?.append(wire[0])
} else {
tree[wire[1]] = [wire[0]]
}
}결과적으로 예시 1번으로 들게되면
// 입출력 예시
var n1: Int = 9
var wires1: [[Int]] = [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]
// 아래와 같이 나열된다.
// 원래 Dictionary는 순서대로 나열되지 않으나, sorted를 사용하여 보기 좋게 나열한 것이다.
1: [3]
2: [3]
3: [1, 2, 4]
4: [3, 5, 6, 7]
5: [4]
6: [4]
7: [4, 8, 9]
8: [7]
9: [7]2. 전력망을 끊기
이제 차례대로 1번에서 만든 트리에서 전력망을 끊어본다.
예시) A-B를 끊자!
1. tree에서 key값이 A인 것의 value B를 제거
2. tree에서 key값이 B인 것의 value A를 제거
// tree 구조에서 하나의 노드를 선택하여 선택된 노드와 연결된 노드들을 모두 한번씩 끊어본다.
tree[base.key] = tree[base.key]?.filter({ $0 != value }) // 해당 조건($0 != value)을 만족하는 요소만 배열에 남겨둠.
tree[value] = tree[value]?.filter({ $0 != base.key })
print("tree[\(base.key)]: \(tree[base.key]) => \(value)가 빠진 형태")
print("tree[\(value)]: \(tree[value]) => \(base.key)가 빠진 형태")위의 내용을 실행해보게 된다면
3번 송전탑, 3번 송전탑 연결된 송전탑: [1, 2, 4]
1번 송전탑, 1번 송전탑 연결된 송전탑: [3]
3번과 1번 송전탑의 전력망을 먼저 끊게 되면
// 위의 print 실행 결과
tree[3]: Optional([2, 4]) => 1가 빠진 형태
tree[1]: Optional([]) => 3가 빠진 형태3. 끊은 전력망 상태에서 송전탑의 차이값 구하기
2번 항목에서 전력망을 끊어서 2개의 송전탑 그룹이 생기는데 각 그룹의 수를 파악하고 그 차이값을 계산해야한다.
- A에서 출발하여 연결된 송전탑의 갯수 파악
- B에서 출발하여 연결된 송전탑의 갯수 파악
이 때, 끊은 전력망을 기준으로 몇개의 송전탑이 연결되어 있는지를 확인한다.
func analysis(_ array: [Int: [Int]], _ start: Int) -> [Int] {
var connectedTower: [Int] = []
var willConnectTower: [Int] = [start] // 시작 지점을 설정한다.
var i: Int = 0
while !willConnectTower.isEmpty { // willConnectTower 비어있으면 종료됨
let node: Int = willConnectTower.removeLast()
// 비어있으면 런타임 에러가 발생하므로 while문 조건에서 비어있는지를 확인한다.
// willConnectTower에서 마지막 요소를 뽑아온 값
// 이미 방문했는지 여부를 판단.
// true일 경우 다음 반복을 진행한다.
// false일 경우 아래줄을 실행한다.
if connectedTower.contains(node) { continue }
// 방문하지 않았으면 방문했었던 기록에 남긴다.
connectedTower.append(node)
willConnectTower += array[node] ?? [] // 반대로 node에 연결된 목록들을 array에서 확인하여 추가한다.
}
return connectedTower // 연결된 목록을 Return 한다.
}실제로 1번 예시를 실행했을 때, 나온 결과를 뽑아보았다.
// 우선 Tree를 나열을 하고
1: [3]
2: [3]
3: [1, 2, 4]
4: [3, 5, 6, 7]
5: [4]
6: [4]
7: [4, 8, 9]
8: [7]
9: [7]
// 첫번째로 전선망을 제거한다.
5번 송전탑, 5번 송전탑 연결된 송전탑: [4] // tree 중에서 key값이 5인 것을 가지고 진행.
4번 송전탑, 4번 송전탑 연결된 송전탑: [3, 5, 6, 7]
// 5와 4사이를 끊겠다.
tree[5]: Optional([]) => 4가 빠진 형태 // 5에서 4를 제거하고 - 해당 value가 빠진 것
tree[4]: Optional([3, 6, 7]) => 5가 빠진 형태 // 4에서 5를 제거한다. - 해당 key가 빠진 것
// 첫번째 항목
// 수정된 tree와 송전탑의 key값인 5를 가지고 온다.
analysis array: [5: [], 8: [7], 2: [3], 4: [3, 6, 7], 6: [4], 7: [4, 8, 9], 3: [1, 2, 4], 1: [3], 9: [7]], start: 5
willConnectTower: [5] // 우선 5에서 출발해야하므로 방문해야되는 순서를 5로 정한다.
node: 5 // willConnectTower에서 마지막 값인 5를 추출한다.
connectedTower.contains(node): false // 이미 지났던 송전탑인지 확인했는데 false! 아니라고 한다.
connectedTower: [5] // 그러면 지나갔다고 추가를 한다.
// 5에서 연결되는 경로를 파악한다.
willConnectTower: [] // 파악해보니 5에서 연결되는 경로가 없다.
결과 start:5, connectedTower: [5] // 송전탑.key가 5인 곳에서 경로는 1개 밖에 없다.
// 두번째 항목
// 수정된 tree와 송전탑의 key값인 5의 value 중에서 4를 가지고 온다.
analysis array: [5: [], 8: [7], 2: [3], 4: [3, 6, 7], 6: [4], 7: [4, 8, 9], 3: [1, 2, 4], 1: [3], 9: [7]], start: 4
willConnectTower: [4] // 우선 4에서 출발해야하므로 방문해야되는 순서를 4로 정한다.
<반복 1번>
node: 4 // willConnectTower에서 마지막 값인 4를 추출한다.
connectedTower.contains(node): false // 이미 지났던 송전탑인지 확인했는데 false! 아니라고 한다.
connectedTower: [4] // 그러면 지나갔다고 추가를 한다.
// 4에서 연결되는 경로를 파악한다.
willConnectTower: [3, 6, 7] // 파악해보니 4에서 연결되는 것은 3,6,7이다.
// willConnectTower가 비어있지 않기 때문에 while문을 반복한다.
<반복 2번>
node: 7 // willConnectTower에서 마지막 값인 7를 추출한다.
connectedTower.contains(node): false // 이미 지났던 송전탑인지 확인했는데 false! 아니라고 한다.
connectedTower: [4, 7] // 그러면 지나갔다고 추가를 한다.
// 7에서 연결되는 경로를 파악한다.
willConnectTower: [3, 6, 4, 8, 9] // 파악해보니 7에서 연결되는 것은 4,8,9이다. 그리하여 기존에 3,6에서 추가를 한다. => [3,6,4,8,9]
// willConnectTower가 비어있지 않기 때문에 while문을 반복한다.
<반복 3번>
node: 9 // willConnectTower에서 마지막 값인 9를 추출한다.
connectedTower.contains(node): false // 이미 지났던 송전탑인지 확인했는데 false! 아니라고 한다.
connectedTower: [4, 7, 9] // 그러면 지나갔다고 추가를 한다.
// 9에서 연결되는 경로를 파악한다.
willConnectTower: [3, 6, 4, 8, 7] // 파악해보니 9에서 연결되는 것은 7이다. 그리하여 기존에 3,6,4,8에서 추가를 한다. => [3,6,4,8,7]
// needVisitStack가 비어있지 않기 때문에 while문을 반복한다.
<반복 4번>
node: 7 // needVisitStack에서 마지막 값인 7를 추출한다.
connectedTower.contains(node): true // 이미 지났던 송전탑인지 확인했는데 true! 지나갔다고 한다.
// needVisitStack가 비어있지 않기 때문에 while문을 반복한다.
...
<반복 15번>
node: 3 // needVisitStack에서 마지막 값인 3를 추출한다.
connectedTower.contains(node): true // 이미 지났던 송전탑인지 확인했는데 true! 지나갔다고 한다.
결과 start:4, connectedTower: [4, 7, 9, 8, 6, 3, 2, 1] // 송전탑의 value 중에서 4와 연결된 것은 8개라고 한다.- 3번과 4번의 결과의 차이값을 구한다. (결과에 절대값을 씌운다)
let cal = abs(analysis(tree, base.key).count - analysis(tree, value).count)- 해당 결과 값이 최저인지 판단하여 최저인 경우 변경. 아닌 경우 기존의 결과 값을 유지.
result = cal < result ? cal : result // 해당 조건이 만족하면 cal로 결정. 아닌 경우 result로 결정4. 다른 전력망도 끊어서 확인하기 위해 전력망 복구하기
전체 전력망을 확인하여 가장 최저인 결과를 얻기 위해서 끊은 전력망을 다시 복구한다.
tree[base.key]?.append(value)
tree[value]?.append(base.key)문제 풀이 후기
생각보다 시간을 많이 소비했던 문제였던 것 같다.
특히, 송전탑 그룹을 나누고 나서 해당 그룹의 갯수를 파악하는 것으르 어떻게 구현해야되는지에 대해 고민을 많이 하게 되었고, 그래프 탐색 알고리즘에 대해서 알게되고 해당 부분에 조금 파게된 코딩 문제였다.
전체 코드
func solution(_ n:Int, _ wires:[[Int]]) -> Int {
// tree에서 특정 송전탑과 이어져 있는 송전탑 목록 표시
var tree: [Int: [Int]] = [:] // [송전탑A: [송전탑A와 연결된 송전탑들]]
// Tree 만들기
for wire in wires {
// wire에서 첫번째 값에 해당되는 내용이 있는가?
if tree[wire[0]] != nil {
tree[wire[0]]?.append(wire[1])
} else {
tree[wire[0]] = [wire[1]]
}
// wire에서 두번째 값에 해당되는 내용이 있는가?
if tree[wire[1]] != nil {
tree[wire[1]]?.append(wire[0])
} else {
tree[wire[1]] = [wire[0]]
}
}
let sortedtree = tree.sorted(by: { $0.key < $1.key })
for (key, value) in sortedtree {
print("\(key): \(value)")
}
var result = wires.count // 처음 전력망의 수를 기준.
for base in tree {
for value in base.value {
// tree 구조에서 하나의 노드를 선택하여 선택된 노드와 연결된 노드들을 모두 한번씩 끊어본다.
// 예시) A-B를 끊자!
// 1. tree에서 key값이 A인 것의 value B를 제거
// 2. tree에서 key값이 B인 것의 value A를 제거
tree[base.key] = tree[base.key]?.filter({ $0 != value }) // 해당 조건($0 != value)을 만족하는 요소만 배열에 남겨둠.
tree[value] = tree[value]?.filter({ $0 != base.key })
print("tree[\(base.key)]: \(tree[base.key]) => \(value)가 빠진 형태")
print("tree[\(value)]: \(tree[value]) => \(base.key)가 빠진 형태")
// 3. A에서 출발하여 연결된 송전탑의 갯수 파악
// 4. B에서 출발하여 연결된 송전탑의 갯수 파악
// 5. 3번과 4번의 결과의 차이값을 구한다. (결과에 절대값을 씌운다)
let cal = abs(analysis(tree, base.key).count - analysis(tree, value).count)
// 6. 해당 결과 값이 최저인지 판단하여 최저인 경우 변경. 아닌 경우 기존의 결과 값을 유지.
result = cal < result ? cal : result // 해당 조건이 만족하면 cal로 결정. 아닌 경우 result로 결정
// 7. 전력망 복구 - 다시 반복을 하기 위해 원래대로 돌린다.
tree[base.key]?.append(value)
tree[value]?.append(base.key)
}
}
return result
}
func analysis(_ array: [Int: [Int]], _ start: Int) -> [Int] {
var connectedTower: [Int] = []
var willConnectTower: [Int] = [start] // 시작 지점을 설정한다.
var i: Int = 0
while !willConnectTower.isEmpty { // willConnectTower 비어있으면 종료됨
let node: Int = willConnectTower.removeLast()
// 비어있으면 런타임 에러가 발생하므로 while문 조건에서 비어있는지를 확인한다.
// willConnectTower에서 마지막 요소를 뽑아온 값
// 이미 방문했는지 여부를 판단.
// true일 경우 다음 반복을 진행한다.
// false일 경우 아래줄을 실행한다.
if connectedTower.contains(node) { continue }
// 방문하지 않았으면 방문했었던 기록에 남긴다.
connectedTower.append(node)
willConnectTower += array[node] ?? [] // 반대로 node에 연결된 목록들을 array에서 확인하여 추가한다.
}
return connectedTower
}
my name is hyeon