크래프톤 정글 3주차 WIL

WIL: Weekly I Learned; 또는 What I Learned This Week

4월은 정글의 거짓말

지난 2주차 WIL을 완성하기가 무섭게 정글이 또 다시 눈밭이 되었습니다. 저는 눈을 참 좋아하지만, 그럼에도 저희 반 친구가 이야기한 것과 같이 지금 코딩을 할 때가 맞을까?라는 생각이 들기도 하는 주였습니다. 기후 변화란 참 무서운 것입니다.

밥만 잘 먹더라

크래프톤은 구내식당이 아주 잘 나오는 것으로 정평이 나 있습니다. 입소 당시 그걸 모르는 것은 아니었지만, 제가 가는 곳은 크래프톤 본사가 아닌 정글 캠퍼스이니, 사실 큰 기대는 하지 않았습니다. 그러나 입소 3주차를 넘기는 이 시점에서 제가 남길 수 있는 말은, 여기 밥도 상당히 맛있다입니다. 입소 첫 며칠간은 일부 메뉴가 (제 입맛에는) 다소간 매워 걱정이 살짝 들기도 했습니다만 어느 순간부터 매운 맛이 점점 납득 가능한 수준으로 내려오더군요. 상당히 만족스럽습니다.

 

3주차에 저희가 탐험한 내용은 크게 세 가지로 나눌 수 있습니다.

자료구조:

• 그래프 (노드, 에지, 가중치, 방향성 등)
• 트리
• Trie
• B-트리 (B-Tree)

알고리즘:

• DFS
• BFS
• Disjoint Set (유니온-파인드 기법)
• 이분 그래프
• 최소 신장 트리 (프림, 크루스칼 알고리즘)
• 위상 정렬
• 최소 비용 계산 (다익스트라, 플루이드-와샬 알고리즘)

마지막으로 CS:APP 책에서는 챕터 1 (개요)의 네트워크, 암달의 법칙, 동시성, 병렬성, 추상화 개념에 대해 학습하였습니다.

이번 시험은 백준 "바닥 장식", "단자번호붙이기", "경쟁적 전염"으로, 1번을 BFS로 풀려다가 30분을 날려먹고 아래와 같은 터무니없이 간단한 이중 for문을 통해 완성하여 제출하였습니다. (놀랍게도 통과가 됩니다!)

import sys
input=sys.stdin.readline

def is_within_bounds(row, col):
    global rows_n, cols_n
    
    return (0<=row<rows_n) and (0<=col<cols_n)

def kazari():
    global rows_n,cols_n,visited,yuka,count
    
    for i in range(rows_n):
        for j in range(cols_n):
            if yuka[i][j] == '-':
                if j == 0 or yuka[i][j-1] != '-':
                    count += 1                    
            elif yuka[i][j] == '|':
                if i == 0 or yuka[i-1][j] != '|':
                    count += 1

# 입력 & 세팅
rows_n, cols_n = map(int,input().split()) # N, M
yuka = [input().strip() for _ in range(rows_n)]
count = 0

# 계산 & 출력
kazari()
print(count)

이번 주차에 배웠던 게 DFS, BFS 같은 것들이라 시험에도 당연히 이를 적용해보려 하였는데, 결국 제대로 된 결과가 나오지 않아 위와 같이 풀고 말았던 것입니다. 사실 이것만 해도 장족의 발전임은 분명합니다. 만약 입소하기 전의 저에게 이 문제를 풀라고 시켰다면 아마 못 풀거나, 적어도 이런 깔끔한 답안은 내지 못했을 것이기 때문입니다.

참고로 위 문제는 분리 집합 (disjoint sets)의 유니언-파인드 방식으로도 풀 수 있습니다.

import sys
input = sys.stdin.readline

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, a, b):
    root_a = find(parent, a)
    root_b = find(parent, b)
    if root_a != root_b:
        parent[root_b] = root_a

# 입력 & 세팅
n, m = map(int, input().split())
yuka = [list(input().strip()) for _ in range(n)]

# 각 셀을 하나의 노드로 표현 (0번부터 n*m-1번까지)
parent = [i for i in range(n * m)]

for i in range(n):
    for j in range(m):
        index = i * m + j
        if yuka[i][j] == '-':
            if j + 1 < m and yuka[i][j + 1] == '-':
                union(parent, index, i * m + (j + 1))
        elif yuka[i][j] == '|':
            if i + 1 < n and yuka[i + 1][j] == '|':
                union(parent, index, (i + 1) * m + j) # 같은 방향의 이웃과 union 처리


unique_roots = set() # 모든 타일에 대해 루트 찾기
for i in range(n * m):
    unique_roots.add(find(parent, i))

print(len(unique_roots))

어쨌든 이 문제와 단자번호붙이기, 총 2개의 문제를 풀어냈다는 점은 좋지만서도, 마지막 문제의 답안을 미처 완성하지 못한 것은 아쉽기도 하고, 그럼에도 불과 3주라는 짧은 기간에도 새삼 많은 것을 배웠다는 것을 느끼게 한 주였습니다.