[백준]230313-19 문제풀이

1107. 리모컨

import sys
input = sys.stdin.readline

def dfs(i, c):
    if i == len(str(N)):
        lst.append(c)
        return
    cnt = 0

    now = int(str(N)[i])
    while cnt < 10:
        if now > 0 and now - cnt in fine:
            dfs(i + 1, c + str(now - cnt))
        if now < 9 and now + cnt in fine:
            dfs(i + 1, c + str(now + cnt))
        cnt += 1

N = int(input())
M = int(input())
broken = list(map(int, input().split()))
fine = []
for i in range(10):
    if i not in broken:
        fine.append(i)

fine.sort()

pre = False
if fine:
    if 0 in fine:
        temp = fine[1:]
        if temp:
            pre = str(min(temp))
    else:
        pre = str(min(fine))

ans = abs(N - 100)

lst = []
dfs(0, '')

for num in lst:
    if abs(int(num) - N) + len(str(N)) < ans:
        ans = abs(int(num) - N) + len(str(N))
    if num[1:] and abs(int(num[1:]) - N) + len(str(N)) - 1 < ans:
        ans = abs(int(num[1:]) - N) + len(str(N)) - 1
    if pre and int(pre+num) <= 500000 and abs(int(pre+num) - N) + len(str(N)) + 1< ans:
        ans = abs(int(pre+num) - N) + len(str(N)) + 1

print(ans)

브루트포싱인데 dfs 함수가 정의되어있는 이유는... 백트래킹으로 풀어보려다가 디버깅의 지옥에 빠져 결국 돌아왔기 때문. 애초에 전부 탐색해야 풀 수 있는 문제고 N이랑 시간 제한을 보고 브루트포싱이라는 걸 생각해냈어야 하는데 어쭙잖게 스킬 써보려다가 된통 당했다. 결국 맞긴 했지만, 너무 구현 풀듯이 케이스 하나하나 조정해준게 코드를 더럽게 만들었다. 같은 스터디에서 투포인터라는 개념으로 풀어낸 분이 있었는데 비교도 안되게 깔끔하고 빨라서 감탄하면서 봤다. 언젠가 다시 돌아봤을 때 좀 더 깔끔하게 풀어낼 수 있었으면 하는 문제.

17609. 회문

import sys
input = sys.stdin.readline

def rev(a):
    for t in range(len(a)//2):
        if a[t] != a[-1-t]:
            return False
    return True

T = int(input())
for tc in range(T):
    inp = input().strip()
    l = 0
    r = len(inp) - 1
    ans = 0
    while l < r:
        if inp[l] == inp[r]:
            l += 1
            r -= 1
        else:
            if rev(inp[l:r]) or rev(inp[l+1:r+1]):
                ans = 1
                break
            else:
                ans = 2
                break
    print(ans)

바로 그 투포인터로 푼 문제. 뭔가 양쪽으로 흩어지거나 모아져야 할 때 시간복잡도를 n으로 할 수 있는 제일 쉬우면서도 간단한 방법인 것 같다. 회문인지 판단할 때 처음에는 ''.join(reversed(str))로 했는데 조금이라도 시간이랑 메모리 덜 잡아먹으려면 반만 탐색하는게 좋을듯해서 저렇게 했는데 테케가 무지막지하게 많지 않은 이상 큰 효과는 없는 듯 하다...

1967. 트리의 지름

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

n = int(input())
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b, c = map(int, input().split())
    adj[a].append([b, c])
    adj[b].append([a, c])

def dfs(now, dis):
    global maxi
    global far
    if dis > maxi:
        maxi = dis
        far = now
    for nxt in adj[now]:
        node, d = nxt
        if not dis_list[node]:
            dis_list[node] = dis + d
            dfs(node, dis + d)

maxi = 0
far = 0
dis_list = [0] * (n + 1)
dis_list[1] = -1
dfs(1, 0)
dis_list = [0] * (n + 1)
dis_list[far] = -1
dfs(far, 0)

print(maxi)

문제에 친절하고 직관적으로 알 수 있게 그림이 나와있는데 방법론을 생각하기가 쉽지 않았다. 결국 dfs 두번이면 끝나는 문제인데, 이 문제에만 국한되는게 아니라 끝단의 노드를 찾는다든지 할 때 유용하게 쓰일만한 방법인 것 같다.

1953. 팀 배분

import sys
input = sys.stdin.readline
from collections import deque

def bfs(i):
    q = deque()
    q.append(i)
    visited[i] = True
    flag = 1
    while q:
        for stu in q:
            if flag:
                blue.append(stu)
            else:
                white.append(stu)
        for _ in range(len(q)):
            now = q.popleft()
            for next in adj[now]:
                if not visited[next]:
                    visited[next] = True
                    q.append(next)
        flag = abs(flag - 1)

n = int(input())
adj = [0]
for i in range(n):
    a, *b = map(int, input().split())
    adj.append(b)

blue = []
white = []
visited = [False] * (n + 1)
for i in range(1, n + 1):
    if not visited[i]:
        bfs(i)
blue.sort()
white.sort()
print(len(blue))
print(*blue)
print(len(white))
print(*white)

나는 bfs로 풀었는데 dfs도 가능하다. 싫어하는 사람을 적팀으로 둔다고 생각하고, 싫어하는 사람의 싫어하는 사람을 다시 반대편으로... 이런식으로 bfs를 해나가다 보면 싫어하는 사람이 겹치지 않고 팀이 배분된다.

5972. 택배 배송

import sys
input = sys.stdin.readline
import heapq
inf = 1e8

N, M = map(int, input().split())
adj = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b, c = map(int, input().split())
    adj[a].append((c, b))
    adj[b].append((c, a))

mini = [inf for _ in range(N + 1)]
mini[1] = 0
heap = []
heapq.heappush(heap, (0, 1))
while heap:
    dist, now = heapq.heappop(heap)
    if mini[now] < dist:
        continue
    for next in adj[now]:
        if mini[now] + next[0] < mini[next[1]]:
            mini[next[1]] = mini[now] + next[0]
            heapq.heappush(heap, [mini[next[1]], next[1]])

print(mini[N])

처음 풀어본 다익스트라 문제. 아직은 조금 생소한 개념이라 익숙하게 쓸 수 있도록 연습이 많이 필요할 것 같다. 매우 전형적인 다익스트라라서 기존 경로에 새 경로를 추가했을 때 최소 경로와 비교해서 계속 업데이트 해주는 방식.

16438. 원숭이 스포츠

import sys
input = sys.stdin.readline

N = int(input())
def dq(a, b, c, flag):
    if c == i:
        if flag:
            for _ in range(a, b):
                print('A', end='')
        else:
            for _ in range(a, b):
                print('B', end='')
        return
    dq(a, (a + b) // 2, c + 1, True)
    dq((a + b) // 2, b, c + 1, False)

for i in range(1, 8):
    if 2 ** (i - 1) >= N:
        cnt = 0
        while cnt < N:
            if cnt < N // 2:
                print('B', end = '')
            else:
                print('A', end = '')
            cnt += 1
        print('')
    else:
        dq(0, N, 0, True)
        print('')

N이 2**7보다 작아서 반반씩 분배하다보면 가능해지겠다고 감 잡아 빨리 푼 문제. 비트마스킹으로도 풀 수 있다고 하는데, 아직 비트마스킹을 몰라서 시도를 못했다. 비트마스킹 연습하러 다시 찾아와야 할 문제.

16236. 아기 상어

from collections import deque
import sys
input = sys.stdin.readline

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

def bfs(y, x):
    global find
    global start
    global dist
    visited = [[False] * N for _ in range(N)]
    visited[y][x] = True
    q = []
    q.append([y, x, 0])
    while q:
        now = q.pop(0)
        if 1 <= lst[now[0]][now[1]] < size:
            find = True
            start = [now[0], now[1]]
            lst[now[0]][now[1]] = 0
            dist = now[2]
            return
        for d in range(4):
            yy = now[0] + dy[d]
            xx = now[1] + dx[d]
            if yy not in range(N) or xx not in range(N):
                continue
            if lst[yy][xx] > size:
                continue
            if visited[yy][xx]:
                continue

            visited[yy][xx] = True
            q.append([yy, xx, now[2] + 1])
            q.sort(key=lambda x: (x[2],x[0],x[1]))

# 입력값
N = int(input())
lst = [list(map(int, input().split())) for _ in range(N)]
# 상어 초기 위치
for i in range(N):
    for j in range(N):
        if lst[i][j] == 9:
            start = [i, j]
            lst[i][j] = 0
size = 2
eat = 0
time = 0
while True:
    find = False
    dist = 0
    bfs(start[0], start[1])
    if not find:
        break
    time += dist
    eat += 1
    if eat == size:
        eat = 0
        size += 1

print(time)

상어 시리즈 구현은 점점 익숙해지고 있다. 사실 구현이라기보단 bfs에 더 가까운 것 같은데 방문할 위치의 우선순위를 정하는게 상당히 난감했다. 시간이 널널해서 queue를 sort해주는 방법을 택했는데 람다 함수로 정렬 기준을 정해주는 법을 잘 알아두면 좋다는 교훈을 준 문제.

2206. 벽 부수고 이동하기

from collections import deque
import sys
input = sys.stdin.readline

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
N, M = map(int, input().split())
MAP = [list(input().strip()) for _ in range(N)]

q = deque()
q.append((0, 0, 0)) # y, x, cnt, wall
visited = [[[0, 0] for _ in range(M)] for __ in range(N)]
visited[0][0][0] = 1
ans = -1
while q:
    now_y, now_x, wall = q.popleft()
    if (now_y, now_x) == (N - 1, M - 1):
        ans = visited[now_y][now_x][wall]
        break
    for d in range(4):
        nxt_y, nxt_x = now_y + dy[d], now_x + dx[d]
        if nxt_y not in range(N) or nxt_x not in range(M):
            continue
        if not wall and MAP[nxt_y][nxt_x] == '1':
            visited[nxt_y][nxt_x][1] = visited[now_y][now_x][wall] + 1
            q.append((nxt_y, nxt_x, 1))
        if not visited[nxt_y][nxt_x][wall] and MAP[nxt_y][nxt_x] == '0':
            visited[nxt_y][nxt_x][wall] = visited[now_y][now_x][wall] + 1
            q.append((nxt_y, nxt_x, wall))

print(ans)

진짜 벽을 부수고 이동할 뻔한 문제. 처음 접근은 쉬웠고, 벽을 부쉈을 때와 부수지 않았을 때의 visited를 다르게 가져가야 한다는 것도 깨달았지만, 방문할때까지의 거리를 따로 넘겨주지 않고 visited에 저장해야 한다는 사실을 끝까지 생각하지 못해서 마지막에 좀 헤맸다. 확실히 고려해야 할 부분이 많아지니 알고 나면 아~ 하는 것도 잘 생각하지 못하게 된다. 코테에서도 분명 이럴텐데... 문제를 많이 풀어보고 다른 사람들 코드를 많이 보면서 여러가지 방법론을 체화해야겠다.

 

요새 자격증, 플젝, 싸피 수업 따라가느라 알고리즘 풀 시간이 너무 부족하다. 선택과 집중을 잘 해야할텐데... 그래도 알고리즘 스터디 덕분에 억지로라도 풀고 있다. 좀만 더 힘내서 1학기 마무리 지어야지...