[프로그래머스] 고득점Kit (10) - 그래프 (파이썬)

1. 가장 먼 노드 (Lv. 3)

# 가장 먼 노드
import sys
MAX = sys.maxsize


def solution(n, edge):
    arr = [[] for _ in range(n+1)]
    for x, y in edge:
        arr[x].append(y)
        arr[y].append(x)
    return go(n, arr)


def go(n, arr):
    visited = [MAX] * (n+1)
    visited[0], visited[1] = 0, 1
    q = []
    q.append(1)
    while q:
        node = q.pop()
        for nnode in arr[node]:
            if visited[nnode] > visited[node] + 1:
                q.append(nnode)
                visited[nnode] = visited[node] + 1
    result = 0
    max_value = max(visited)
    for x in visited:
        if x == max_value:
            result += 1
    return result

 

BFS로 보다 쉽게 풀 수 있었지만, 그래프 파트에 맞게 접근을 했다.

시작을 1로 지정해주고 다음 노드의 값이 업데이트될 값보다 크다면 간선을 타고 넘어가서 1씩 더해 주었다.

단순 그래프 탐색으로 해결을 하였다.

 

마지막에 max값 개수를 return

---

2. 순위 (Lv. 3)

# 순위
def solution(n, results):
    arr = [[0] * (n+1) for _ in range(n+1)]
    for x, y in results:
        arr[x][y] = 1
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                if arr[i][j] == 0 and arr[i][k] and arr[k][j]:
                    arr[i][j] = 1
    result = 0
    for i in range(1, n+1):
        sum = 0
        for j in range(1, n+1):
            if i != j:
                sum += arr[i][j] + arr[j][i]
                if sum == n-1:
                    result += 1
    return result

 

순위를 매길 수 있는 선수의 숫자를 구하는 것 : 하나의 노드가 각 노드와 모두 연결이 되어 있으면 순위를 매길 수 있다.

최대 100명이므로 3중 for문인 플로이드 와샬 알고리즘의 시간 복잡도를 만족한다.

플로이드 와샬 : i가 j를 이긴다면 1로 초기화를 해준다.

이후, i와 연결된 모든 노드를 탐색하면서

(i가 이기는 선수의 수) +  (i가 지는 선수의 수) 가 n-1(자신 제외)이면 자기 자신의 위치를 안다는 뜻

 

예전에 백준에서 같은 문제를 접했어서 쉽게 풀었다.

[백준] 2458번 - 키 순서

[백준] 2458번 - 키 순서 (파이썬)

---

3. 방의 개수 (Lv. 5)

# 방의 개수
from collections import deque
from collections import defaultdict as dfd
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]


def solution(arrows):
    start = (0, 0)
    visited = dfd(bool)
    lines = dfd(bool)
    q = deque()
    q.append(start)
    for k in arrows:
        x, y = start
        nx, ny = x, y
        for _ in range(2):
            nx += dx[k]
            ny += dy[k]
            start = (nx, ny)
            q.append(start)

    answer = 0
    node = q.popleft()
    visited[node] = True
    while q:
        nnode = q.popleft()
        if visited[nnode]:
            if not lines[(node, nnode)]:
                answer += 1
        else:
            visited[nnode] = True
        lines[(node, nnode)] = True
        lines[(nnode, node)] = True
        node = nnode
    return answer

 

어려워서 풀이를 봤다. 가장 핵심이 되는 것은

1. 정점이 아닌 곳에서 선분이 교차하는 경우이다.

이를 방지하기 위해서 (1칸씩 이동 -> 2칸씩 이동)으로 바꿔준다.

2. 방문 했던 정점을 재방문하고, 해당 선분이 이미 존재하는 선분이 아니라면 새로운 도형이 그려진다.

이는 해시를 이용해서 나름 간단하게 풀 수 있다.

 

3번 문제는 일주일 후 다시 풀어볼 문제 리스트에 넣어놨다.

오늘도 문제에 전방위로 후두려 맞았다.

 

---

프로그래머스 고득점 Kit를 전부 풀어보았다.

조금 더 프로그래머스식 문제에 익숙해지기 위해

이제 1Lv~3Lv 문제를 와장창 풀어볼 예정이다.