[Swift] 가장 먼 노드

[문제]

코딩테스트 연습 - 가장 먼 노드 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

[문제 풀이]

bfs를 이용해서 쉽게 풀 수 있는 문제이다.

처음에 입력이 주어질때 edge 값을 graph[edge[i][0]] 에 edge[i][1] 들을 넣으면 graph[1] 안에 2와 3이란 값이 순서대로 들어가 있다.

이걸 양방향으로 처리해주고 반복문을 이용해서 1부터 순서대로 노드를 가까운 순서대로 방문하자.

그렇게 방문하다가 마지막 거리일때 answer를 반환해주면 된다.

[회고]

첨에는 단순히 graph[20002][20002]를 만들어서 풀었는데 해당 방식으로는 최악의 경우 20,000 * 20,000번을 방문해야 해서 시간초과가 났다.

그래서 이와 같이 graph[1] 안에 2, 3.... 식으로 넣는걸 생각할 수 있었다.

swift로 코테를 푸는게 오랜만이라 순간 안 익숙했는데 어느정도 감을 찾기까지 얼마 안 걸릴 것 같다.

일주일동안 swift로 코테를 풀면서 감을 되찾자!

[코드]

import Foundation

struct Queue<T> {
    private var queue = [T]()
    
    public mutating func push(_ element: T) {
        queue.append(element)
    }
    
    public mutating func pop() -> T? {
        return isEmpty ? nil : queue.removeFirst()
    }
    
    public func front() -> T? {
        return isEmpty ? nil : queue.first
    }
    
    public var size: Int {
        return queue.count
    }
    
    public var isEmpty: Bool {
        return queue.isEmpty
    }
}

var graph = Array(repeating: [Int](), count: 20002)
var visited = [Int](repeating: 0, count: 20001)

func bfs(_ n : Int) -> Int {
    var answer = 0
    var q = Queue<(Int,Int)>()
    q.push((1,0))
    visited[1] = 1
    var num: Int = 0
    
    while q.size > 0 {
        var cur: Int = q.front()?.0 ?? 0
        var cnt: Int = q.front()?.1 ?? 0
        q.pop();
        answer += 1
        if num != cnt {
            num = cnt
            answer = 1
        }
        for i in graph[cur] {
            if visited[i] == 1 {
                continue
            }
            visited[i] = 1
            q.push((i,cnt + 1))
        }
    }    
    return answer
}

func solution(_ n:Int, _ edge:[[Int]]) -> Int {
    var answer: Int = 0
    
    for i in edge {
        graph[i[0]].append(i[1])
        graph[i[1]].append(i[0])
    }
    
    answer = bfs(n)
    
    return answer
}