정글사관학교 25일차 TIL: 마음을 다잡는 글 + 경쟁적 전염(#18405), 트리(#4256)

오늘도 어김없이 찾아오는 시험날. 이번 주차는 망이다...ㅎ.. 자꾸 출가하는 멘탈을 억지로 억지로 잘 붙잡다가도 다잡기가 쉽지 않았다. 설상가상으로 정글 1기 관련 소식을 접하고 나니 더욱 마음이 불안해진다. 이럴 때는 책만큼 좋은 도구가 없다. 박지웅 대표의 <이기는 게임을 하라>는 책이 요즘 화젯거리다. 바로 오늘 푼 문제 정리부터 하려다 말고 잠깐 책을 읽었다.

 

맞다. 깜빡하고 있었다. 분명 이 길을 선택할 때 이기는 게임을 한다는 확신이 있었다. 커리어를 전향하는데 6개월을 절대 넘기지 않겠다는 자신이 있었다. 정글은 그 시작이었다. 하지만 정글이라는 판 하나 가지고 100%라는 승률이 나오겠나. 이길 수 있는 판을 짰다면 나머지는 내 몫이다. 압도적인 양과 전략으로 승부한다.

 

목표를 잘 생각하자. 내 목표는 개발자로서 회사에 입사하는 것이지 오늘 알고리즘 다 맞추는 게 아니다. 알고리즘 문제를 한방에 다 이해하고 휘리릭 풀 수 있다면 얼마나 좋겠냐만 그만한 머리를 타고나지 못했다는 걸 인정하자. 다행이라면 알고리즘을 잘 이해하고 푸는 것과 별개로 취업에서는 코테를 통과할 수준만 넘으면 그 다음부터는 또 다른 전략을 필요로 한다.(참고글) 물론 여기까지는 도달할 수 있도록 열심히 해야겠으나, 수학적 사고력은 내 강점이 아니기 때문에 다른 쪽에서 승부를 봐야 한다. 알고리즘을 열심히 공부하되 이거 아니면 안된다는 생각은 늘 경계하자. 극단은 늘 사람을 불안하게 한다. 오늘 이 문제 제 시간에 하나 못 푼다고 떨어지는 거 아니다. 절박하되 조급하지 말자. 그럼 TIL 시작!

 

1. 경쟁적 전염(#18405)

 

문제 링크는 여기.

 

오늘 시험 시간을 싹다 잡아먹은 거지같은 문제.. 테케는 싹다 통과인데 왜 자꾸 오답이 뜨는지 당최 이해할 수가 없었다.

 

내가 풀었던 풀이 방식에서는 가장 낮은 순번의 바이러스부터 bfs를 돌아야 하니 heapq를 사용했다. 다시 리뷰하면서 heapq 때문에 오답이라고 생각했는데 그게 아니라 visited를 체크하면서 새로 추가된 바이러스에도 visited를 1로 표기해서 한 번 이상부터는 아예 돌지 않았던 게 문제. 말로 설명하기보다 코드를 아래 붙여넣기 한다. 결과적으로 heapq 자체의 문제는 아닌 것으로 판단. 

 

from sys import stdin
import heapq


n, k = map(int, stdin.readline().split())
pipe = [list(map(int, stdin.readline().split())) for _ in range(n)]
S, X, Y = map(int, stdin.readline().split())
virus = [[] for _ in range(k+1)]

for i in range(n):
    for j in range(n):
        if pipe[i][j] != 0:
            v = pipe[i][j]
            virus[v].append([i, j])

visited = [[0]* n for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(S):
    cnt = 0
    while True:
        if cnt == S:
            return pipe[X-1][Y-1]
        
        hq = []
        for x in range(n):
            for y in range(n):
                if  not visited[x][y] and pipe[x][y] !=0: => 여기가 문제의 그 부분!
                    val = pipe[x][y]
                    heapq.heappush(hq, (val, x, y))
                    visited[x][y] = 1
        while hq:
            val, a, b = heapq.heappop(hq)            
            for m in range(4):
                nx = a + dx[m]
                ny = b + dy[m]
                if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and pipe[nx][ny] == 0:
                    pipe[nx][ny] =val
                    visited[nx][ny] = 1
        
        cnt += 1
                        

ans = bfs(S)
print(ans)

하지만 아래 붙여넣은 정답을 보면 그냥 queue를 사용해도 비교적 깔끔하게 풀이가 가능하다. 이때 핵심은 전체는 while문을 돌리되 새로 추가된 바이러스만큼만 반복문을 돌리고 cnt+=1을 추가하고 싶을 때는 for문에서 range(len(q))를 이용해 딱 원하는 만큼만 돌리는 방식을 쓰면 된다는 점! 자세한 내용은 아래 코드에.

 

"""1번 문제"""

from sys import stdin
from collections import deque


n, k = map(int, stdin.readline().split())
pipe = [list(map(int, stdin.readline().split())) for _ in range(n)]
S, X, Y = map(int, stdin.readline().split())
virus = [[] for _ in range(k+1)]

for i in range(n):
    for j in range(n):
        if pipe[i][j] != 0:
            v = pipe[i][j]

visited = [[0]* n for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

q = []
for x in range(n):
    for y in range(n):
        if not visited[x][y] and pipe[x][y] !=0:
            val = pipe[x][y]
            q.append((val, x, y))
            visited[x][y] = 1


cnt = 0
while True:
    if cnt == S:
        break
    q = deque(sorted(list(q)))
    for _ in range(len(q)): # len(q) 쓰기: 딱 제한적인 횟수로 돌리기에 아주 good!
        value, a, b = q.popleft()            
        for m in range(4):
            nx = a + dx[m]
            ny = b + dy[m]
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and pipe[nx][ny] == 0:
                pipe[nx][ny] =value
                visited[nx][ny] = 1
                q.append((value, nx, ny))
    cnt += 1

ans = pipe[X-1][Y-1]
print(ans)

"""오답노트
1. 작은 값 가진 바이러스부터 출발해야 한대서 heapq 돌린 것 => q 받아서 sort 처리하기! heapq는 계속 작은 애만 나와서 놉.
2. while문으로 계속 돌린 것=> for문 돌릴 때 len(q)쓰기!
"""

 

2. 트리(#4256)

시험 때는 문제를 제대로 쳐다도 보지 못했다만..다시 보면 의외로 간단하다. 핵심은 preorder에서 루트를 찾고 inorder에서 해당 루트가 어디 위치해있는지를 찾으면 우리는 루트와 루트 기준 왼쪽 자식 트리, 오른쪽 자식 트리를 알 수 있다. 그걸 고대로 받아다가 postorder를 돌리면 끝!

 

"""2번 문제"""
from sys import stdin, setrecursionlimit
setrecursionlimit(10**9)


def postorder(preorder, inorder):
    
    #종료 조건: len(preorder)가 2이하일 때
    if len(preorder) == 0:
        return # 왼쪽 자식 노드가 더이상 없음.
    elif len(preorder) ==1: # 노드 자신 뿐임.
        print(preorder[0], end = ' ')
        return
    elif len(preorder) == 2:
        print(preorder[1], preorder[0], end = ' ')
        return
    
    #노드 개수가 3이상부터면 재귀로 쪼갠다. 왼쪽/오른쪽/자기자신을 구분짓고 왼쪽/오른쪽 각각에 대해 재귀 돌리면 오케이
    root = preorder[0] # preorder[0]은 자기 자신!
    div = inorder.index(root)
    
    #여기서부터 재귀
    postorder(preorder[1:div+1], inorder[0:div])
    postorder(preorder[div+1:], inorder[div+1:])
    print(preorder[0], end = ' ')

test_num = int(stdin.readline())

for _ in range(test_num):
    node_num = int(stdin.readline())
    preorder = list(map(int, stdin.readline().split()))
    inorder = list(map(int, stdin.readline().split()))
    postorder(preorder, inorder)
    print()

 

 

3번까지 공부할 힘이 없어 오늘은 여기까지..고생했다...!