아스

문제

https://school.programmers.co.kr/learn/courses/30/lessons/1844

풀이

그래프 형식의 문제이니만큼 그래프 탐색을 이용했고, BFS로 풀었습니다. 

우선 BFS에 필요한 큐를 구현하기 위해서 collections 라이브러리의 deque 자료구조를 사용했습니다.

일반 리스트로도 pop(0) 메소드를 통해 큐의 역할을 구현할 수는 있지만 이 경우 맨 앞의 원소를 제거할 때는 O(n) 시간이 걸린다는 단점이 있어서 deque() 라이브러리를 사용했습니다. 

from collections import deque

def solution(maps):
    
    m = len(maps)
    n = len(maps[0])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    def bfs(start_x, start_y, end_x, end_y):
    	# 거리 정보를 저장하는 배열. 시작점에서 닿을 수 없는 경우 -1의 값을 가짐
        dist = [[-1] * n for _ in range(m)]
        Q = deque([(start_x, start_y)])
        dist[start_x][start_y] = 1
        
        while Q:
            cur_x, cur_y = Q.popleft()
            for k in range(4):
                nx = cur_x + dx[k]
                ny = cur_y + dy[k]
                
                # 배열 인덱스를 벗어나는 경우
                if nx < 0 or nx >= m or ny < 0 or ny >= n:
                    continue
                    
                # 벽인 경우
                elif maps[nx][ny] == 0:
                    continue
                    
                # 한 번도 방문하지 않은 경우만 큐에 추가
                # 최단거리로 방문하려면 같은 블럭을 두 번 이상 방문하는 일은 없어야 한다.
                if dist[nx][ny] == -1:
                    dist[nx][ny] = dist[cur_x][cur_y] + 1
                    Q.append((nx, ny))
                    
        return dist[end_x][end_y]
    
    return bfs(0, 0, m-1, n-1)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/258705

참고한 가이드

카카오 기술 블로그에 나온 풀이 방법을 참고했습니다.

해당 블로그의 5번 문제에 풀이 과정이 잘 설명되어 있으니 궁금하신 분은 참고하시면 좋을 것 같습니다. 

https://tech.kakao.com/2023/12/27/2024-coding-test-winter-internship/

풀이

해당 풀이에서는 DP(dynamic programming) 방법을 설명해주셔서 배열을 선언한 뒤 각 인덱스에 점화식을 적용하는 방식으로 풀었습니다. 

def solution(n, tops):
    a = [0] * (n+1)
    b = [0] * (n+1)
    a[0] = 0
    b[0] = 1
    for i in range(1, len(a)):
        a[i] = (a[i-1] + b[i-1]) % 10007
        if tops[i-1] == 1:
            b[i] = (2 * a[i-1] + 3 * b[i-1]) % 10007
        else:
            b[i] = (a[i-1] + 2 * b[i-1]) % 10007
    answer = (a[n] + b[n]) % 10007
    return answer

직관적으로는 모든 값을 이중 for문으로 순회하면서 능력치를 계산하는 방법이 있다. 

그러나 이 방법으로 하면 시간초과가 난다. 

리스트의 전체 값을 순회해야 하는데 정석대로 하면 시간초과가 나는 경우, 투 포인터를 사용해서 접근해볼 수 있다. 

능력치는 (두 개발자 사이에 있는 개발자 수) * (두 개발자의 능력치 중 작은 값)으로 계산되므로, left와 right이라는 두 포인터를 리스트의 양 끝에 배치시켜서 두 개발자 사이에 있는 개발자 수를 최대로 만들어 보자. 

그리고 두 포인터가 가리키는 값 중에서 누가 더 작은지를 비교해서, 더 작은 쪽의 값을 변화시키는 방식으로 포인터를 이동해 나간다. 

left 쪽의 값이 더 작다면 left를 한 칸 오른쪽으로, right의 값이 작다면 right를 한 칸 왼쪽으로 이동하는 식이다. 

그러면 이중 for문의 풀이는 O(n^2)였던 데 비해, 투 포인터로 O(n)에 풀 수 있어서 시간초과가 나지 않는다. 

import sys

input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))

answer = 0
left, right = 0, N-1
while left < right:
    cur = (right-left-1) * min(arr[left], arr[right])
    answer = max(cur, answer)
    if arr[left] > arr[right]:
        right -= 1
    else:
        left += 1

print(answer)

식의 값을 최소로 만드는 방법은 처음으로 -가 나왔을 때, 그 - 뒤의 값은 모두 빼는 것이다. 

따라서 입력을 받은 수식에서 첫 번째 -가 몇 번째 인덱스에 존재하는지를 찾고, 그 인덱스를 기준으로 앞의 값은 A, 뒤의 값은 B라고 하자. 

그러면 A-B가 수식에서 나올 수 있는 최소 값이 된다. 만약 -이 없다면 식에서 숫자 값들만 추출해준 뒤 그 값들을 모두 더해주면 된다. 

풀이

import sys
input = sys.stdin.readline

commands = input()
if commands.find("-") == -1:
    nums = list(map(int, commands.split("+")))
    print(sum(nums))
else:
    index = commands.find("-")
    a = commands[:index]
    b = commands[(index+1):]
    sum_a = sum(list(map(int, a.split("+"))))
    sum_b = sum(list(map(int, b.replace("+", "-").split("-"))))
    print(sum_a-sum_b)

그래프는 2차원 배열이나 collections 라이브러리의 defaultdict() 타입으로 선언해준다. 

bfs 방식으로 그래프를 탐색하되, 각 시작점마다 dist 배열을 선언해서 해당 노드를 탐색하기까지 몇 개의 노드를 거쳤는지를 표시해주고, sum()으로 그 거리들을 모두 더해준다. 

이때 sum() 0번째 노드를 제외하는 이유는 노드는 1번째 부터 N번째까지 있기 때문이다. 

마지막으로 각 노드마다 get_dist라는 bfs 탐색을 하는 함수를 호출하면서 값을 비교하고, 거리의 합이 더 작은 노드를 min_number 값으로 바꿔 주면서 for문을 1번 순회하면 된다. 

풀이

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

N, M = map(int, input().split())
graph = defaultdict(list)

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
def get_dist(num):
    dist = [-1] * (N+1)
    dist[num] = 0
    Q = deque([num])
    while Q:
        elem = Q.popleft()
        for node in graph[elem]:
            if dist[node] == -1:
                Q.append(node)
                dist[node] = dist[elem] + 1
    return sum(dist[1:])

min_dist = sys.maxsize
min_number = 101

for i in range(1, N+1):
    bacon_dist = get_dist(i)
    if bacon_dist < min_dist:
        min_dist = bacon_dist
        min_number = i
    elif bacon_dist == min_dist:
        min_number = min(i, min_number)
        
print(min_number)

리스트의 매 원소마다 해당 원소보다 작은 고유한 원소들이 몇 개인지 세서 계산하는 방식을 쓰면 시간 초과가 나는 문제였다. 

prefix sum 방식과 유사하게, 해당 원소보다 작은 개수인 고유한 원소의 개수가 몇 개인지를 미리 unique_list 배열에 저장해 두고, 정답 배열에 이 값을 추가하는 방식으로 시간초과를 막을 수 있었다. 

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

N = int(input())
arr = list(map(int, input().split()))

unique_list = defaultdict(lambda: 0)
for index, a in enumerate(sorted(list(set(arr)))):
    unique_list[a] = index

ans = []
for a in arr:
    ans.append(str(unique_list[a]))
    
print(" ".join(ans))

bfs 또는 dfs 방식으로 그래프를 탐색하면 된다. 

만약 모든 노드가 이어져 있다면, 즉 연결 요소의 개수가 1개라면 그래프 탐색으로 모든 노드를 방문할 수 있을 것이다. 

그게 아니라면 연결 요소의 개수만큼 그래프를 탐색해야 모든 노드를 방문할 수 있을 것이다. 

u, v 노드 사이의 간선을 저장하는 방법은 2차원 배열도 있고 여러 가지가 있으나, 여기서는 collections.defaultdict()을 사용해서 딕셔너리에 노드 값 하나와 노드와 이어진 다른 노드들의 리스트를 키-값으로 맵핑하였다. 

또한 여기서는 그래프의 모든 노드를 순회하면서, 방문하지 않은 노드가 있을 경우 그 노드를 시작점으로 bfs 탐색을 진행하였다. 

한 번 탐색할 때마다 연결 요소의 개수도 증가하므로 ans 변수의 값을 1씩 증가시켰다. 

import sys
from collections import defaultdict, deque

input = sys.stdin.readline
N, M = map(int, input().split())
graph = defaultdict(list)
visited = [False] * (N+1)

for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
    
def bfs(start):
    Q = deque([start])
    visited[start] = True
    while Q:
        node = Q.popleft()
        for n in graph[node]:
            if not visited[n]:
                visited[n] = True
                Q.append(n)

ans = 0
for i in range(1, N+1):
    if not visited[i]:
        bfs(i)
        ans += 1

print(ans)

그래프를 탐색하되, bfs나 dfs처럼 연쇄적으로 탐색하지 말고 한 번에 근처에 있는 주변 노드들만 탐색한다. 

연쇄적으로 한 번에 탐색하면 안 되는 이유는 총 탐색하는데 며칠이 걸리는지를 알아내야 하기 때문이다. 

따라서 데크(deque)를 선언하고 인접한 노드를 데크에 추가하는 bfs의 방식을 활용하되, 데크에 새로 인접한 노드들을 추가하지는 않았다. 

즉 한 번 bfs()를 실행할 때마다 익은 토마토 주변의 토마토만 익게 된다. bfs() 함수에서는 배열의 값이 0인 칸들만 1로 바꿔주는 것으로 이를 대신하였다. 

배열의 값이 -1인 경우는 토마토가 없는 것이므로 인접한 토마토가 익는 효과가 나타나지 않는다. 그러므로 배열의 값이 꼭 0일 때만 1로 만들어 주어야 한다. 

ripe_list라는 변수를 선언해서 맨 처음에 익어 있는 토마토를 해당 변수에 추가한다. 

이후에는 bfs()를 실행하면서 맨 처음에 익어 있는 토마토에 의해 새로 익게 된 토마토만 ripe_list 변수에 추가해 준다. 

이런 방식으로 while 문을 실행하면서, 새로 익게 되는 토마토가 없는 경우 탐색을 종료한다. 

while 문에서는 day 값을 1씩 늘려가면서 탐색한다. 이때 day 값을 0으로 하면 0번째 값을 탐색할 때에도 day 값이 1씩 추가되기 때문에, day 값을 -1로 두고 시작한다. 

새로 익게 되는 토마토가 없는 경우, 즉 ripe_list의 값이 없는 경우 while 문을 빠져나오고 난 뒤에는 전체 배열을 순회하면서 값이 0인 칸을 탐색한다. 

만약 값이 0인 칸이 있다면 익지 않은 토마토가 있다는 뜻이므로 토마토가 모두 익지 못한 것이다. 이 경우에는 -1을 출력하고, 나머지 경우에는 while문으로 값을 증가시킨 day 값을 출력한다. 

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

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

def bfs(ripe):
    Q = deque(ripe)
    new_ripe = []
    while Q:
        x, y = Q.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if nx >= N or nx < 0 or ny >= M or ny < 0:
                continue
            if arr[nx][ny] == 0:
                arr[nx][ny] = 1
                new_ripe.append([nx, ny])
    return new_ripe

M, N = map(int, input().split())
arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))
    
ripe_list = []
for i in range(N):
    for j in range(M):
        if arr[i][j] == 1:
            ripe_list.append([i, j])

day = -1
while ripe_list:
    ripe_list = bfs(ripe_list)
    day += 1

ripe = True
for i in range(N):
    for j in range(M):
        if arr[i][j] == 0:
            ripe = False
            break
if not ripe:
    print(-1)
else:
    print(day)