오늘 배운 것들

1. BFS(계속)

1-1. 0-1 BFS

일반 BFS($O(V+E)$)를 최단 거리를 구하기 위해서 사용하려면 모든 간선의 가중치가 같아야 한다.(무가중치)
가중치가 있는 경우 특정 출발점에서의 최단 거리를 구하는 문제에서는 일반적으로 다익스트라 알고리즘($O(ElogV)$)이 사용된다.
그러나 가중치가 0 또는 1로만 주어진 경우에도 한 가지 스킬만 추가하면 BFS를 사용할 수 있다.
큐 대신 덱을 사용하고 가중치가 0인 간선으로 이동할 때에는 덱의 앞에 삽입해주면 된다.
0 가중치로 방문할 수 있는 노드들을 우선 모두 방문하게 되므로, 하나의 노드를 방문한 것과 같은 효과를 얻을 수 있다.

1-2. 최소 비용 구하기(백준 1916)

import sys
from collections import deque
import heapq

input = sys.stdin.readline
INF = 100000001

def main() -> None:
    def dijkstra(start, end) -> None:
        cost_list = [None] + [INF] * N
        visited = [None] + [False] * N
        priority_q = [(0, start)]
        cost_list[start] = 0
        now = start
        while now != end:
            now = heapq.heappop(priority_q)[1]
            if visited[now] == True:
                continue
            visited[now] = True
            for to in buses[now]:
                if not visited[to]:
                    new_cost = cost_list[now]+buses[now][to]
                    if new_cost < cost_list[to]:
                        cost_list[to] = new_cost
                        heapq.heappush(priority_q, (new_cost, to))
        print(cost_list[end])
    
    N = int(input())
    M = int(input())
    buses = {i: {} for i in range(1, N+1)}
    for i in range(M):
        frm, to, cost = map(int, input().split())
        buses[frm][to] = cost if to not in buses[frm] else min(cost, buses[frm][to])
    start, end = map(int, input().split())
    
    dijkstra(start, end)
    
if __name__ == "__main__":
    main()

다익스트라 알고리즘을 구현하는 문제.
간선의 중복 여부를 꼭 체크해야 한다.
위 코드에서는 간선 입력을 받을 때 중복을 제거하도록 구현하였다.

BFS를 사용할 때에는 꼭 큐에 넣기 전 중복 체크를 하여야 한다.

1-3. 미로 만들기(백준 2665)

import sys
from collections import deque

input = sys.stdin.readline
di = (1, 0, 0, -1)
dj = (0, 1, -1, 0)

def main() -> None:
    # MAP를 1칸씩 확장하는 함수
    def expand(map):
        for i in range(N):
            for j in range(N):
                for d in range(4):
                    new_i, new_j = i+di[d], j+dj[d]
                    if not all((0<=new_i<N, 0<=new_j<N)):
                        continue
                    MAP[i][j] += map[new_i][new_j]
            
    # map_cur를 전체 방으로 맞춰주는 함수
    def check_room(map: list, edge: deque) -> deque:
        # visited = map
        q = edge.copy()
        edge = deque()
        q.append((0, 0))
        # (q.append(i) for i in edge)
        while q:
            cur = q.popleft()
            flag = False
            for d in range(4):
                new_i, new_j = cur[0]+di[d], cur[1]+dj[d]
                if not all((0<=new_i<N, 0<=new_j<N)):
                    continue
                if MAP[new_i][new_j] != 0:
                    if map[new_i][new_j] == 0:
                        map[new_i][new_j] = 1
                        q.append((new_i, new_j))
                else:
                    flag = True
            if flag:
                edge.append(cur)
        return edge
        
    N = int(input())
    MAP = [list(map(int, list(input().rstrip()))) for _ in range(N)]
    map_cur = [[0]*N for _ in range(N)]
    map_cur[0][0] = 1
    edge = deque()
    
    n_change = 0
    edge = check_room(map_cur, edge)
    while map_cur[N-1][N-1]==0:
        n_change += 1
        expand(map_cur)
        edge = check_room(map_cur, edge)
    print(n_change)
main()

길이 완전히 이어져있지 않은 미로에서 몇 개의 방을 열린 방으로 바꿔야 도착할 수 있는지를 구하는 문제.
처음에는 이어진 한 방들을 하나의 정점으로 하여, 가중치 그래프를 만들어 풀어보려 했지만 그래프를 만드는 것이 너무 복잡할 것 같아서 포기.
한 개의 방만 바꿔서 갈 수 있는 곳부터 따져볼까 하는 생각이 들었다.
어차피 되돌아 가거나 여러 경로가 나오더라도 최단 거리만 구하면 되니까 방을 조금씩 확장해 가면 되지 않을까하는 아이디어로 구현했다.
시작지점에서 하나로 이어진 방들(시작방들)을 상하좌우로 한 칸씩 넓히고 새롭게 이어진 방들이 있다면 시작방들에 포함시킨다.
도착지점이 연결될 때까지 넓힌 횟수가 문제의 답이 된다.
0-1 BFS을 이용해 풀 수도 있을 것 같지만 구현은 나중에 연습해봐야 겠다.

1-4. 토마토(백준 7569)

import sys
from collections import deque

input = sys.stdin.readline

di = (1, 0, 0, -1, 0, 0)
dj = (0, 1, -1, 0, 0, 0)
dk = (0, 0, 0, 0, 1, -1)

def main() -> None:
    def age(q: deque) -> None:
        next_q = deque()
        while q:
            k, i, j = q.popleft()
            for d in range(6):
                new_i, new_j, new_k = i+di[d], j+dj[d], k+dk[d]
                if all((0<=new_i<N, 0<=new_j<M, 0<=new_k<H)):
                    if A[new_k][new_i][new_j]==0:
                        A[new_k][new_i][new_j] = 1
                        next_q.append((new_k, new_i, new_j))
        return next_q
    
    def check_zero():
        for k in A:
            for i in k:
                for j in i:
                    if j == 0:
                        return True
        return False

    M, N, H = map(int, input().split())
    A = []
    q = deque()
    n_0 = 0
    for k in range(H):
        A.append([])
        for i in range(N):
            A[k].append([])
            for j, e in enumerate(input().split()):
                e = int(e)
                A[k][i].append(e)
                if e == 1:
                    q.append((k, i, j))
                elif e == 0:
                    n_0 += 1
    count = 0
    while q:
        q = age(q)
        if q:
            count += 1
    if check_zero():
        print(-1)
    else:
        print(count)
    
main()

어제에 이어 또또 다른 무식한 bfs문제.
익은 토마토에서부터 시작하여 새롭게 익은 토마토만 큐에 넣어 확인하는 것이 시간초과를 피하는 포인트
무식하게 박으면 풀릴 줄 알고 시간을 많이 버렸다.

1-5. 탈출(백준 3055)

import sys
from collections import deque

def main() -> None:
    def water_expand(waters: list) -> list:
        next_waters = []
        while waters:
            curr_w = waters.pop()
            for d in range(4):
                new_i, new_j = curr_w[0]+dx[d], curr_w[1]+dy[d]
                if all((0<=new_i<R, 0<=new_j<C)):
                    if A[new_i][new_j] not in ['D', 'X', '*']:
                        A[new_i][new_j] = '*'
                        next_waters.append((new_i, new_j))
        return next_waters
    def move_hedgehogs(hedgehogs: list) -> list | None:
        next_hedgehogs = []
        while hedgehogs:
            curr_h = hedgehogs.pop()
            if A[curr_h[0]][curr_h[1]] == '*':
                continue
            for d in range(4):
                new_i, new_j = curr_h[0]+dx[d], curr_h[1]+dy[d]
                if all((0<=new_i<R, 0<=new_j<C)):
                    if A[new_i][new_j] not in ['*', 'X', 'S']:
                        if A[new_i][new_j] in ['D']:
                            return None
                        A[new_i][new_j] = 'S'
                        next_hedgehogs.append((new_i, new_j))
        return next_hedgehogs
    
    input = sys.stdin.readline
    dx = (1, 0, 0, -1)
    dy = (0, 1, -1, 0)
    hedgehogs = []
    waters = []
    count = 0
    
    R, C = map(int, input().split())
    A = []
    for i in range(R):
        A.append([])
        for j, a in enumerate(list(input().rstrip())):
            A[i].append(a)
            if a == '*':
                waters.append((i, j))
            elif a == 'S':
                hedgehogs.append((i, j))
    
    while True:
        count += 1
        hedgehogs = move_hedgehogs(hedgehogs)
        if not hedgehogs:
            break
        waters = water_expand(waters)
    if hedgehogs is None:
        print(count)
    else:
        print("KAKTUS")
        
if __name__ == "__main__":
    main()

고슴도치와 물이 동시에 퍼져야 하는, bfs 두 개를 동시에 할 뿐인 또또또 무식한 bfs문제.
12행에 이미 물이 있는 경우에는 다음 확인할 리스트에 넣지 말아야 했는데 그걸 빼먹어서 메모리 초과가 계속 떴었다.

# 수정 전
if A[new_i][new_j] not in ['D', 'X']:
# 수정 후
if A[new_i][new_j] not in ['D', 'X', '*']:

2. 2주차 퀴즈 정리

1. 캐시 메모리를 사용하면 컴퓨터 시스템의 성능이 왜 향상되는지 지역성(locality) 개념을 포함하여 설명하시오.

지역성은 프로그램이 메모리를 접근할 때 특정 부분을 집중적으로 사용하는 경향을
나타냅니다. 이는 두 가지 형태로 나타납니다:

• 시간적 지역성(Temporal Locality)
  한 번 접근된 데이터는 가까운 미래에 다시 접근될 가능성이 높다는 원리입니다.
  예를 들어, 루프 내에서 반복적으로 사용되는 변수는 시간적 지역성의 좋은 예입니다.
• 공간적 지역성(Spatial Locality)
  메모리의 특정 주소에 접근한 후, 그 주변 주소에 있는 데이터에 접근될 가능성이 높다는 원리입니다.
  이는 배열이나 연속적인 메모리 블록에 접근할 때 종종 발생합니다.

캐시 메모리는 이러한 지역성 원리를 활용하여 자주 사용되거나 연속적으로 사용될 가능성이 높은 데이터를 미리 캐시에 저장합니다.
이로 인해 CPU는 필요한 데이터를 캐시에서 빠르게 찾을 수 있습니다.

2. 프로세스와 쓰레드의 차이를 설명하세요. (시스템자원,독립vs공유 키워드로 설명하면 됩니다.아래는예시입니다.)

정의:

• 프로세스: 독립적으로 실행되는 프로그램의 인스턴스로, 자체적인 주소 공간,
  메모리, 데이터 스택 및 다른 시스템 자원을 갖습니다.
• 쓰레드: 프로세스 내부의 실행 흐름 단위로, 프로세스의 자원과 주소 공간을
  공유하면서 실행됩니다.

자원 공유:

• 프로세스: 각 프로세스는 독립적인 메모리 공간과 시스템 자원을 가지므로,
  프로세스간 자원 공유는 IPC (Inter-Process Communication) 메커니즘을 통해
  이루어집니다.
• 쓰레드: 같은 프로세스 내의 쓰레드들은 코드, 데이터 및 시스템 자원을 공유합니다.

소감

bfs는 재미가 없다.