Ray`s Tech Lab

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

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

예제 입력 1 

5

1 3 2 -1

2 4 4 -1

3 1 2 4 3 -1

4 2 4 3 3 5 6 -1

5 4 6 -1

예제 출력 1 

11

 우선 결론적으로, 트리의 지름에 대해 알아야 풀 수 있는 문제다.

 처음에는 1을 루트노드로 잡고 DFS를 돌려서 가장 먼 거리의 노드를 구하면 그 노드까지의 거리가 트리의 지름이겠다 싶었는데, 풀다보니 "도대체 어떤 노드를 루트노드로 해줘야 가장 먼 거리의 노드까지의 거리가 트리의 지름이 될 것인가?"라는 문제에 봉착했다. 그러다가 임의의 노드(x) 하나를 루트노드로 잡고 거기서 가장 먼 거리의 노드를 구한 후, 구한 노드를 루트 노드로 잡고 거기서 다시 먼 노드를 구했을 때 구한 노드가 바로 전에 돌렸던 DFS에서의 루트노드라면 그 거리가 최장거리이지 않을까라는 생각을 하게 됐다. 왜냐하면 어쨌든 최장거리가 될 수 있는 후보들은 끝 노드와 끝 노드간의 거리들이기 때문이다. A가 만약 끝점이고, 여기서 가장 먼 거리의 노드가 B일 때 B에서 가장 먼 끝점도 A면 A와 B사이의 거리가 최장거리가 된다는 것. 근데 만약 B에서 가장 먼 거리의 노드가 A가 아니라면 A가 끝점이 아니거나, A까지의 거리보다 더 먼 거리를 가지는 끝점이 있거나 둘 중 하나가 되는 것이다.

 그럼 처음에 내 맘대로 루트노드를 1로 잡고 DFS를 돌려서 가장 먼 거리의 노드를 찾고, 다시 그 노드를 루트노드로 잡고 DFS를 돌려서 찾은 노드가 전에 돌렸던 DFS의 루트노드와 같다면, 그 때 측정한 거리가 루트의 지름이다!는 것을 알 수 있는데, 이렇게 연속된 두 번의 DFS결과를 비교하며 트리의 지름을 찾는 방식은 비효율적일것 같았다. 막말로 DFS를 몇 번 돌리게 될지도 모르는건데..그래서 그냥 루트의 지름에 대해서 공부했다.

참고한 링크 : https://blog.myungwoo.kr/112

요악하자면, 처음에 임의의 노드 하나를 루트노드로 잡고 가장 먼 거리의 노드를 찾은 다음, 그 녀석을 다시 루트노드로 잡고 가장 먼 거리의 노드를 찾으면 그 노드와의 거리가 트리의 지름이란 말이다.

암튼 뭐..그래서 코드는 다음과 같다.

import sys
sys.setrecursionlimit(10**6) # RecursionError 방지

V = int(sys.stdin.readline())
Tree = [[] for i in range(V + 1)]

for i in range(V):
    c = list(map(int, sys.stdin.readline().split()))
    for j in range(1, len(c) - 1, 2):
        Tree[c[0]].append([c[j], c[j + 1]])  # 각 노드에 연결된 노드와 간선의 길이 표현


def DFS(Tree, start_node, distance):
    for node, dis in Tree[start_node]:
        if not distance[node]:               # node까지 가는 거리가 0이라면 (기록되지 않았다면)
            distance[node] = distance[start_node] + dis  # node까지 가는 거리 기록
            DFS(Tree, node, distance)

distance = [0 for i in range(V + 1)]
DFS(Tree, 1, distance)
distance[1] = 0   # distance는 start_node에서 각 노드까지의 거리를 저장하는 리스트이므로, 자기 자신에서 출발해 자기 자신까지의 거리는 0으로 해야 함.

start_node, max_distance = -1, -1
        # 무지성으로 max(distance)를 하면 가장 먼 거리는 알 수 있는데, 어떤 노드까지의 거리
        # 인지는 모르게 돼서, 이렇게 선형탐색같은 방법으로 가장 먼 거리를 가지는 노드를 찾음
                                       
for i in range(1, V + 1):
    if distance[i] > max_distance:
        max_distance = distance[i]
        start_node = i

distance = [0 for i in range(V + 1)]
DFS(Tree, start_node, distance)
distance[start_node] = 0                  # distance는 start_node에서 각 노드까지의 거리를 저장하는 리스트이므로, 자기 자신에서 출발해 자기 자신까지의 거리는 0으로 해야 함.
print(max(distance))

 이걸 풀면서 배운 것은 배열을 통한 트리의 표현방법과, 재귀를 통한 DFS방법.

트리의 지름도 조만간 정리해서 올려야지.

분리집합(Disjoint Set)이란 서로 중복되지 않는 부분집합들로 나뉜 원소들에 대한 정보를 다루는 자료구조이다. Union-Find 알고리즘은 이 자료구조를 활용하는 대표적인 그래프 알고리즘 중 하나로, '합집합을 찾는다'라는 의미를 가진다. 디테일하게 들어가면 원소 x, y를 고른 다음 x가 속한 집합과 y가 속한 집합이 같은지 판별하는 알고리즘안대, 이는 여러 노드가 존재할 때 내가 선택한 임의의 두 노드가 서로 같은 그래프에 속하는지 판별한다는 것과 같은 개념으로 생각할 수 있다.

그냥 내가 이해한대로 쉽게(나름대로) 설명하자면, Union-Find알고리즘과 분리집합은 집합을 표현하는 하나의 형태이다. 1부터 5까지의 원소들이 있고 이들이 각각 집합의 형태를 이루고 있다고 하자. 즉,

{1}, {2}, {3}, {4}, {5}

이렇게 있는 것이다. 근데 이를 표를 통해 다음과 같이 표현할 수 있다.

{1}의 입장에서 자기가 속한 집합의 리더는 자기 자신(1)이고, {2}나 다른 애들 입장에서도 마찬가지다. 즉 표를 통해 자신이 속한 집합의 리더를 나타내준것! 근데 여기서 {1}과 {2}가 만나서 합집합 {1, 2}를 만들어냈다고 하자. 1과 2가 같은 집합의 원소로 구성된 것이다. 현재 존재하는 집합들은

{1, 2}, {3}, {4}, {5}

인 것이다. 이는 방금과 같은 표를 통해 어떻게 표현할 수 있을까?

다른 건 변함없고 2만 변화가 생겼다. 자신이 속한 그룹의 리더가 1이 된 것! 사실 뭐 2를 리더로 할 수도 있지만..집합을 이루는 원소 중 가장 작은 놈을 리더로 뽑는 것이다. 쉽게 생각해서 2는 1이 이끄는 집합의 멤버가 된 것이라고 생각해도 된다. 만약 다른 애들도 서로 합치고 지지고 볶고 해서 집합들이 다음과 같이 됐다면?

{1, 2}, {3, 4, 5}

표는 다음과 같아질 것이다.

그럼 생각해보자. 내가 임의로 두 원소를 뽑았는데 그 놈이 2랑 4다. 이들이 각각 속한 집합은 같은가?

표를 통해서 다르다는 것을 알 수 있다. 왜 Why? 2는 1이 이끄는 집합에 속해있고, 4는 3이 이끄는 집합에 속해있기 때문이다. 서로가 속한 집합의 리더가 다르기 때문에 이들이 속한 집합은 서로 다른 집합이다라고 말할 수 있는 것이다. 이것이 Union-Find알고리즘이다. 

근데 Union Find알고리즘은 여러 노드가 존재할 때 두 노드를 선택해서 이 두 녀석이 같은 그래프에 속하는지 판별하는 것으로도 이해할 수 있다고 했다. 간단하다. 단지 집합으로 표현하던 걸 그래프로 나타낼 때 Union Find가 저렇게 표현될 뿐이다. 1~5까지의 각 원소들이 집합의 형태를 이루고 있는 상태를, 1~5까지의 노드들이 서로 연결되지 않고 존재하는 상태라고 이해하면 된다. 그리고 집합들이 합쳐지는 것은 노드들 간에 연결선이 생겨서 연결되는 것으로 생각하면 된다. 따라서 내가 고른 임의의 두 노드가 서로 같은 그래프에 존재하는지 확인하는 것은 각각의 root노드들을 확인해서 같으면 같은 그래프 상에 존재하는 것이다! ...사실 이 부분은 글로만 써서 이해가 잘 안 될 수도 있으니 공부할 때 참고한 나동빈 님의 영상을 링크로 걸어두겠다.

https://www.youtube.com/watch?v=AMByrd53PHM 

그럼 Union Find를 파이썬으로 구현해보자.

parant = [i for i in range(n + 1)]

def getParant(x):         # x의 부모를 리턴하는 함수
    if parant[x] == x:    # x의 부모가 자기자신이라면 x를 그대로 리턴
        return x        
    parant[x] = getParant(parant[x])  # x의 부모가 자기자신이 아님 -> 재귀호출로 x의 부모 재설정
    return parant[x]                  # 최종적으론 x의 부모 리턴
    
def union(x, y):        # x가 속한 집합과 y가 속한 집합 합치기 - 가장 부모을 비교해 더 작은 쪽으로 합침
    x, y = getParant(x), getParant(y)
    if x < y:           # x가 더 작으니까 y의 부모를 x로
        parant[y] = x
    elif x > y:         # y가 더 작으니까 x의 부모를 y로
        parant[x] = y

def hasSameParant(x, y):         # x, y가 같은 부모를 같는지 즉 같은 집합에 속해있는지
    x, y = getParant(x), getParant(y)
    if x == y:
        return "YES"
    else:
        return "NO"

리더로 표현하던 것을 부모로 표현하는 것에만 차이가 있다. getParant함수가 이 알고리즘의 핵심으로 자신의 부모가 자기자신이 아니라면 재귀호출을 통해 자신의 부모를 최상단 노드, 즉 집단 내에서 가장 작은 놈으로 설정해준다.  이를 통해 백준 사이트에서 대표적으로 다음과 같은 문제를 풀 수 있다.

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

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

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

예제 입력 1 복사

10

15 5 1 3 5 10 7 4 9 2 8

예제 출력 1 복사

2

[접근방식]

1. 배열의 첫 번째 원소부터 시작해 합이 S 이상이 되는 가장 짧은 구간의 길이를 구한다.

2. 배열의 두 번째 원소부터 시작해 합이 S 이상이 되는 가장 짧은 구간의 길이를 구한다.

3. 배열의 세 번째 원소부터 시작해 합이 S 이상이 되는 가장 짧은 구간의 길이를 구한다.

...이렇게 해서 각 단계에서 구한 길이 중 가장 짧은 놈을 고른다.

import sys

N, S = map(int, sys.stdin.readline().split())
length = []

arr = list(map(int, sys.stdin.readline().split()))

for i in range(len(arr)):
    j, sum = i + 1, arr[i]

    while(sum < S and j < len(arr)):
            sum += arr[j]
            j += 1
    if sum >= S:
        length.append(j - i)

if length:
    print(min(length))
else:
    print(0)

근데 위 코드는 시간초과가 발생한다. 왜일까?

우선 코드를 보면 난 for문에서 i를 시작점으로 설정하며 각 구간들을 구하는데, j라는 변수가 구간의 끝점역할을 한다. 따라서 구하는 구간의 합이 S이상이 되는 순간 구간의 길이인 j - i를 length리스트에 더하고 마지막에 min메소드로 가장 짧은 길이를 출력하면 그것이 정답이다. 근데 시간초과가 뜨는 이유는 다름아닌 j, sum와 관련되어 있다.

바로 매 순간 새로 측정을 시작할 때마다(즉 시작점 i가 바뀔 때마다) j를 i + 1로 세팅한 뒤, j를 늘려가면서 측정하기 때문! 이것이 시간을 잡아먹는다. 마찬가지로 sum을 매 측정마다 새로 설정해주는 것도 시간을 잡아먹는다. 왜 Why?

어떤 단계에서 합이 S이상이 되는 구간을 구했다고 할 때, 이 구간의 끝점이 있다.

다음 단계에서 합이 S이상이 되는 구간을 또 구할텐데, 이 때 새로 구하게 되는 구간의 끝점은 이전 단계에서 구한 구간의 끝점보다 같거나 클 수밖에 없기 때문! 따라서 매 측정의 단계에서 사용한 j와 sum을 그대로 재활용?하는 느낌으로 써주는 식으로 코드를 수정했다.

import sys

N, S = map(int, sys.stdin.readline().split())
length = []

arr = list(map(int, sys.stdin.readline().split()))
sum_arr, j = arr[0], 1

for i in range(len(arr)):           
    while(sum_arr < S and j < len(arr)):   
        sum_arr += arr[j]             
        j += 1
    if sum_arr >= S:                       
        length.append(j - i)
    sum_arr -= arr[i]                     

if length:                                
    print(min(length))
else:                                      
    print(0)

이런 방식?을 투포인터 알고리즘 이라 부르는 것 같다.

공부해봐야겠다..

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

문제

민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB

이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.

폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 500이다.

출력

첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.

예제 입력 1 복사

XXXXXX

예제 출력 1 복사

AAAABB

예제 입력 2 복사

XX.XX

예제 출력 2 복사

BB.BB

[내가 한 풀이]

boards = input().split('.')
answer = ''

for board in boards:
    if len(board) % 2 == 1:
        print(-1)
        break
    else:
        if len(board) >= 4:
            answer += 'AAAA' * (len(board) // 4)
        answer += 'BB' * ((len(board) % 4) // 2) + '.'
else:
    print(answer[:-1])

입력으로 받은 전체 보드판(?)을 split()메소드를 활용해 온점(.)을 기준으로 나눠서 리스트로 만든다.

이후 리스트에 대해 순회하는데, 나는 AAAA와 BB라는 폴리오미노만 갖고 있으므로 홀수칸짜리 보드판에 대해서는 폴리오미노를 덮을 수 없다. 이 경우는 2로 나눈 나머지가 1인 경우에 해당하며, 이땐 -1을 출력하고 break.

보드판이 짝수칸이라면 몇 칸인지에 관계없이 폴리오미노로 덮을 수 있는데, 2칸일 경우에만 처음부터 바로 BB를 채우고 2칸이 아니라면 그냥 무지성으로 AAAA만 신나게 깔아주다가 마지막에 2칸만큼 남으면 BB를 덮으면 된다. 어차피 if-else 이하의 코드는 순회한 보드가 짝수칸일테만 실행되므로, 4칸 이상일 때는 보드칸을 4로 나눈 몫만큼 AAAA를 덮어주고, 이후 나머지 칸에 대해 BB를 덮어준다. AAAA를 다 덮고 남은 칸은 len(board) % 4이다. 

마지막엔 출력할 차례. 순회하는 모든 보드판이 죄다 짝수칸이었다면 break문에 의해 비정상적으로 for문이 종료되지 않았으므로 마지막의 for-else문의 print가 실행된다. 이때 answer의 마지막은 온점(.)이므로 슬라이싱하여 그 전까지만 출력하면 정답이다. 

[더 쉬운 풀이]

board = input()
board = board.replace("XXXX", "AAAA")
board = board.replace("XX", "BB")
if 'X' in board:
    board = -1
print(board)

replace메소드를 활용해 처음엔 문자열 내에 등장하는 모든 XXXX를 AAAA로 바꾸고, 이후 다시 문자열 내에 등장하는 모든 XX를 BB로 바꿔주고, 마지막에 X가 남아있다면 -1을 출력하도록 한다.

replace메소드는 replace(old, new, count) 총 3개의 파라미터를 받으며 old는 현재 문자열에서 바꾸고 싶은 놈, new는 새로 바꿀 문자, count는 정수를 받으며 변경할 횟수를 의미한다. count는 optional로 입력하지 않으면 문자열 전체의 old를 new로 바꾼다.

그래프같은 걸 탐색할 때, 너비를 우선으로 탐색을 진행하는 것을 너비우선탐색, 영어로는 Breadth First Search라고 하며 줄여서 BFS라고도 부른다. 어떠한 시작점이 있을 때, 그로부터 가까운 것들부터 탐색해나가는 방법으로 맹목적인 탐색을 할 때 사용가능한 방법이다. 이 녀석은 '최단 경로'를 찾아주기 때문에 최단길이를 보장해야 할 때 많이 쓰인다.

예시)

이 방법을 구현하려면, 큐(queue)가 필요하다.

그럼 이걸 파이썬으로 구현해보자.

우선 그래프는 다음과 같이 딕셔너리 형태로 표현해봤다.

graph = {
    1 : [2, 3, 4],
    2 : [1, 3],
    3 : [1, 2, 4, 5],
    4 : [1, 3],
    5 : [3, 6],
    6 : [5]
}           # 키에 연결된 value에 있는 리스트가 그 key에 연결된 애들임

그리고 BFS를 도와줄 큐는 다음과 같이 해보자.

queue = []                       # 큐를 리스트 형태로 구현

queue.append(something)          # 큐에 요소를 넣는 동작 : append  ->큐의 뒤쪽에 추가
queue.pop(0)                     # 큐에 요소를 빼는 동작 : pop(0)  ->큐의 앞쪽에 있는 걸 뺌

 그럼 BFS를 다음과 같이 만들 수 있다.

def BFS(graph, start_node):
    visited = []                           # 방문한 요소들이 이 리스트에 저장됨
    queue = [start_node]                   # 큐

    while queue:                           # 큐에 뭔가 있는 동안 이하 내용을 반복한다
        node = queue.pop(0)                # 큐의 제일 앞에 있는 놈을 빼와서
        if node not in visited:            # 만약 이 놈이 방문한 적이 없다면
            visited.append(node)           # 방문처리
            print(node)                    # 그 녀석 출력
            queue.extend(graph[node])      # 그 녀석과 연결된 요소들(graph[node])를 queue에 추가

근데 이 방법에는 문제점이 있다.

그것을 확인하기 위해 다음과 같이 코드 중간중간에 print를 써서 현재 queue와 visited에 있는 값들을 하나하나 확인해보고,  걸리는 시간까지 알아보자.

import time

def BFS(graph, start_node):
    start = time.time()
    visited = []
    queue = [start_node]

    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            print(node)
            print(f'방문 처리 후 visited : {visited}')
            queue.extend(graph[node])
            print(f'큐에 연결된 요소 추가 후 queue : {queue}')
        print("-"*10)
    print(time.time()-start)

대략 0.007초가 걸렸다.

이 코드의 문제점은 그럼 뭘까?

어떤 요소를 방문처리해주고(visited.append(node))

그 요소와 연결된 요소들(graph[node])를 큐에 추가해줄 때, 방문한 적 없는 요소들만 추가해야 한다.

근데 위 코드는 일단 연결된 요소들 전부 큐에 추가해주고, 나중에 큐에서 꺼낼 때 꺼낸 값이 방문한 적이 있는지 없는지를 판단하기 때문에 쓸데없이 시간을 낭비하는 꼴이 된다.

그래서 다음과 같이 바꿔줄 수 있다.

def BFS(graph, start_node):
    visited = []
    queue = [start_node]

    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            print(node)
            for nd in graph[node]:             # 연결된 요소들에 대해 하나하나 따진다
                if nd not in visited:          # 방문한 적 없는 요소여야
                    queue.append(nd)           # 큐에 추가

그러나 이 방법도 문제점이 있다. 큐에 원소들을 추가해주는 작업을 하는 부분을 보면 graph[node]에 해당하는 리스트의 원소들을 루프문으로 돌기 때문에, 시간낭비가 역시 생길 수 있다!

이 문제점을, set이라는 자료형를 사용해 상당히 간편하게 해결할 수 있다.

그래서 다음과 같이 해준다.

def BFS(graph, start_node):
    visited = []
    queue = [start_node]

    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            print(node)
            queue += (set(graph[node]) - set(visited))

그러나 아직까지도 문제가 있다..ㅋㅋㅋㅋㅋㅋ

큐에서 제일 첫 번째 녀석을 빼주는 queue.pop(0)이 문젠데, 이 녀석의 시간복잡도가 O(n)이라는 것.

이는 collection 라이브러리에 있는 deque를 사용해 해결가능하다.

그리고 visited가 리스트로 되어있는데,

if in 또는 if not in방법은 리스트에서 하면 이 역시 시간복잡도가 O(n)이다.

따라서 visited를 딕셔너리 또는 집합(set)으로 해주는 게 더 빠르다!

그래서, 다음과 같이 해주자.

from collections import deque

def BFS(graph, start_node):
    visited = {}
    queue = deque([start_node])

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited[node] = True
            print(node)            
            queue += (set(graph[node]) - set(visited))