Coding 공부

import sys
import heapq
def distra(start,ind):
    distance[ind][start] = 0
    node_list = []
    heapq.heappush(node_list,(0,start))
    while node_list:
        dis,node = heapq.heappop(node_list)
        if dis > distance[ind][node]:
            continue
        for next_node in graph[node]:
            if distance[ind][next_node] > dis + graph[node][next_node]:
                distance[ind][next_node] = dis + graph[node][next_node]
                heapq.heappush(node_list,(distance[ind][next_node],next_node))
input = sys.stdin.readline

N, E = map(int,input().split())
graph = [{} for i in range(N+1)]

for _ in range(E):
    A,B,C = map(int,input().split())
    graph[A][B] = C
    graph[B][A] = C

ess = list(map(int,input().split()))

INF = float('inf')
distance = [[INF]*(N+1) for _ in range(3)]

distra(1,0)
distra(N,1)
distra(ess[0],2)

a = distance[0][ess[0]] + distance[1][ess[1]] + distance[2][ess[1]]

b = distance[0][ess[1]] + distance[1][ess[0]] + distance[2][ess[1]]
result = min(a,b)
if result == INF:
    print(-1)
else:
    print(result)

이 문제는 다익스트라를 이용해서 푸는 문제이다. 대신 입력으로 주어진 두 정점을 무조건 통과 해야하는 문제였다.

그렇기 때문에 두가지 경로로 가능하다고 생각했다.

시작점 : 1번노드 /  도착점 : N번노드 경유노드 : A,B번 노드

라고 하겠다.

1번노드 ->A번노드 -> B번노드 -> N번노드

1번노드 ->B번노드 -> A번노드 -> N번노드

라고 생각했다.

이 두 가지 경로에 대해서 구하고, 둘중의 최저값이 정답이 된다.

이걸 한번에 구하기 위해, 총 3번의 다익스트라를 해주었다.

distance라는 2차원 배열을 만들어두고, 열은 전체 distance를 넣어주는 역할을 하고,

0번 행은 1번노드에서의 다익스트라

1번 행은 N번 노드에서의 다익스트라

2번 행은 A번 노드에서의 다익스트라

가 저장되게 해놓았다.

그래서 각각의 경로에 맞게 더해주기만 하면 되고,

만약 최저값이 INF로 나올시, A,B번 노드를 동시에 통과하는 경우는 없는 것이므로, -1을 출력하도록 했다.

백준 골드1을 달성했다.

매일 1문제 이상씩 알고문제를 풀고 있는데 아직 블로그에 올리지 못한 문제들이 많다..

빨리 올려야겠다.

import sys


input = sys.stdin.readline
def roll(A,B):
    if A[0] >= B[0] and A[1] < B[1]:
        dx = A[0]-B[0]
        dy = B[1]-A[1]
        return (B[0]+dy,B[1]+dx)
    elif A[0] >= B[0] and A[1] >= B[1]:
        dx = A[0] - B[0]
        dy = A[1] - B[1]
        return (B[0]-dy,B[1]+dx)
    elif A[0] < B[0] and A[1] < B[1]:
        dx = B[0]-A[0]
        dy = B[1]-A[1]
        return (B[0]+dy,B[1]-dx)
    else:
        dx = B[0]-A[0]
        dy = A[1]-B[1]
        return (B[0]-dy,B[1]-dx)



def dragon(cur_gener,total_gener):
    global dragon_list
    if cur_gener == total_gener:
        return

    tail_position = dragon_list[-1]
    dragon_length = len(dragon_list)
    for ind in range(dragon_length-2,-1,-1):
        dragon_list.append(roll(dragon_list[ind],tail_position))
    dragon(cur_gener+1,total_gener)




N = int(input())
# x,y 시작점 d는 시작 방향 g는 세대 

dx = [1,0,-1,0]
dy = [0,-1,0,1]
arr = [[0]*101 for i in range(101)]
for _ in range(N):
    x,y,dire,gener = map(int,input().split())
    dragon_list = [(x,y),(x+dx[dire],y+dy[dire])]
    if gener:
        dragon(0,gener)
    for position in dragon_list:
        arr[position[1]][position[0]] = 1

result = 0



for y in range(100):
    for x in range(100):
        if arr[x][y] + arr[x+1][y] + arr[x+1][y+1] + arr[x][y+1] == 4:
            result += 1

print(result)

이 드래곤 커브는 끝에 있는 점을 기준으로 현재까지 온 경로들을 전부 시계 방향으로 90도 회전을 해주는 것을 계속 반복한다.

처음 풀었던 방식은 어렵게 생각해서 푼 문제이다.

드래곤 커브의 각 점들의 위치를 한 리스트에 넣어준다. 그러면 끝점을 찾아주고, 그 끝점을 기준으로 끝점을 제외한 나머지 점들의 위치를 파악해서, 옮겨주는 작업을 해주었다. 

좌표계로 그려보면 알겠지만, 끝점을 원점으로 생각해서, 그 점을 기준으로 1,2,3,4 사분면에 있을때 회전하는 위치를 계산해주었다.

1사분면에 있으면 1사분면의 y축 값은 x축값이 되고, x축의 값은 +y축값이 된다. 

2사분면에 있으면 2사분면의 x축값은 +y축값이 되고, y축값은 -x축 값이 된다.

이런식으로 구분을 해서, 각 끝점을 기준으로 움직인 위치를 찾아서 드래곤 커브 리스트에 넣어준다.

여기서 주의 해야할 점은 두가지인데, 문제에 주어진 xy좌표축은 수직방향으로 위로 올라갈수록 y축 값이 줄어드는 것이다.

그리고 두번째는 끝점을 기준으로 뒤에서부터 판별을해야 한다는 것이다.

이렇게 모든 세대를 돌리고 난뒤에 101*101 행렬에 점을 찍어주면 된다. 그리고 마지막으로 네 귀퉁이에 전부 1인 경우에를 세어서 결과로 출력하면 된다.

import sys

input = sys.stdin.readline

N = int(input())

arr = [[0]*101 for _ in range(101)]
dx = [1,0,-1,0]
dy = [0,-1,0,1]
for _ in range(N):
    x,y,dire,gener = map(int,input().split())
    # dire 0 ->1
    # 1->2
    # 2->3
    # 3->0
    move_list = [dire]
    arr[y][x] = 1
    for _ in range(gener):
        temp = []
        for i in range(len(move_list)-1,-1,-1):
            temp.append((move_list[i]+1)%4)
        move_list.extend(temp)
    for i in move_list:
        nx = x + dx[i]
        ny = y + dy[i]
        arr[ny][nx] = 1
        x,y  = nx,ny
result = 0
for y in range(100):
    for x in range(100):
        if arr[y][x] + arr[y+1][x] + arr[y][x+1] + arr[y+1][x+1] == 4:
            result += 1
print(result)

좀 더 쉬운 풀이는 다음과 같다.

진행방향만 넣어주는 것이다.

90도 시계방향을 회전하면 다음 진행반향은 현재 진행방향의 +1 의 modulo 4 연산을 해주면 된다.

이렇게 move_list에 넣어주고, 위에서처럼 끝점부터 해서 넣어주면 된다.

그리고 모든 세대를 지난뒤에, 처음시작점에서 진행방향에 맞춰서 점을 찍어주면 된다.

import sys

input = sys.stdin.readline

N = int(input())

arr =[ list(map(int,input().split())) for _ in range(N)]

max_arr = [[0]*3 for _ in range(2)]
min_arr = [[0]*3 for _ in range(2)]

max_arr[0][0] = min_arr[0][0] = arr[0][0]
max_arr[0][1] = min_arr[0][1] = arr[0][1]
max_arr[0][2] = min_arr[0][2] = arr[0][2]

for i in range(1,N):
    max_arr[1][0] = arr[i][0] + max(max_arr[0][0],max_arr[0][1])
    max_arr[1][1] = arr[i][1] + max(max_arr[0][0],max_arr[0][1],max_arr[0][2])
    max_arr[1][2] = arr[i][2] + max(max_arr[0][1],max_arr[0][2])
    min_arr[1][0] = arr[i][0] + min(min_arr[0][0],min_arr[0][1])
    min_arr[1][1] = arr[i][1] + min(min_arr[0][0],min_arr[0][1],min_arr[0][2])
    min_arr[1][2] = arr[i][2] + min(min_arr[0][1],min_arr[0][2])

    for y in range(3):
        max_arr[0][y] = max_arr[1][y]
        min_arr[0][y] = min_arr[1][y]

print(max(max_arr[0]),min(min_arr[0]))

처음 풀어본 슬라이딩 윈도우 관련 문제이다. 들어오는 N의 최대값이 10만이므로, 그대로 전체에 대해서 행렬을 만들경우, 메모리 초과가 날 수 있다.

그럴때 사용하는 알고리즘인 것 같다.

슬라이딩 윈도우에 관련된 설명은 blog.fakecoding.com/archives/algorithm-slidingwindow/ 에서 공부했다.

이 문제도 슬라이딩 윈도우를 통해, 최대값과 최소값을 갱신해주면 되는 문제이다.

일단 한 행에는 3개의 인수가 나와있고, 그 행에서 최대값을 얻을 수 있는 경우는

첫번째 열은 첫번째 열과 값과 그전 행의 첫번째 열과 두번째 열 중 더 큰 값을 더하는 경우이고,

두번째 열은 두번째 열의 값과 그전 행의 첫번째, 두번째, 세번째 열 중  가장 큰 값과 더해주는 것이다.

세번째 열은 세번째 열의 값과 그전 행의 두번쨰,세번째 열 중 가장 큰 값과 더해주는 것이다.

구해진 값들은 현재 행의 각 열에서의 최대값을 구한것이다. 그러면 이 다음행은 이 전전 행 현재행의 그전 행의 값의 유무는 상관이 없다. 현재행의 값들만 알고 있으면 위의 로직을 다음행에서 진행할때에는 전전행은 필요가 없으므로, 현재행에서 구한 값들의 위치를 이전행으로 옮겨주는 과정을 하면 된다.

최소값은 max에서 min으로 바꿔주기만 하면 된다.

import sys
import heapq

input = sys.stdin.readline

N = int(input())
M = int(input())
graph = [{} for i in range(N)]

for _ in range(M):
    a,b,c = map(int,input().split())
    if a != b:
        graph[a-1][b-1] = c
        graph[b-1][a-1] = c

INF = float('inf')
distance = [INF]*N
visited = [False] *N
distance[0] = 0
node_list = []
heapq.heappush(node_list,(0,0))
result = 0
while node_list:
    dis, node = heapq.heappop(node_list)
    if visited[node]:
        continue
    result += dis
    visited[node] = True
    for next_node in graph[node]:
        if distance[next_node] > graph[node][next_node]:
            distance[next_node] = graph[node][next_node]
            heapq.heappush(node_list,(distance[next_node],next_node))

print(result)

최소 스패닝 트리 문제이다. 프림알고리즘과 크루스칼 알고리즘이 있는데, 크루스칼 알고리즘에 아직 익숙하지 않아, 프림 알고리즘으로 구현했다.

heapq를 이용해서 구현했기 때문에, distance가 갱신될때에만 heapq.heappush를 해주는 것만 주의해주면 풀 수 있는 문제이다.

import heapq
import sys
input = sys.stdin.readline
N,M = map(int,input().split())

arr = [list(map(int,list(input().strip()))) for _ in range(M)]

node_list = []
heapq.heappush(node_list,(0,0,0))
INF = float('inf')
dp = [[INF]*N for _ in range(M)]
dx = [-1,1,0,0]
dy = [0,0,1,-1]
dp[0][0] = 0
while node_list:
    dis,x,y = heapq.heappop(node_list)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<M and 0<=ny<N:
            if dp[nx][ny] > dp[x][y] + arr[nx][ny]:
                dp[nx][ny] = dp[x][y] + arr[nx][ny]
                heapq.heappush(node_list,(dp[nx][ny],nx,ny))

print(dp[M-1][N-1])

BFS를 이용해서 푸는 방법도 있을것 같은데, 다익스트라로 풀었다. 기본적으로 하는 BFS와 동일하다. 대신 2차원으로 바뀌었기 때문에, 4방향을 탐색하면, 현재 dp값이 줄어드는 경우에만 heapq에 push를 해주고, 여기서는 거리대신 해당 arr에 있는 벽의 유무로 판별해주었다.

import sys

input = sys.stdin.readline
n = int(input())
INF = float('inf')
graph = [[INF if i !=j else 0 for j in range(n)] for i in range(n)]
m = int(input())

for _ in range(m):
    A,B,C = map(int,input().split())
    graph[A-1][B-1] = min(graph[A-1][B-1],C)
for k in range(n):
    for start in range(n):
        for end in range(n):
            if graph[start][end] > graph[start][k] + graph[k][end]:
                graph[start][end] = graph[start][k] + graph[k][end]



for row in graph:
    print(*[j if j != INF else 0 for j in row])

플로이드 와샬을 이용한 문제였다.

2차원 배열을 자기자신을 가는 경우를 제외한 나머지 경우를 INF로 초기화 시켜주고, 들어오는 input에서도 같은 경로를 여러번 들어오는 경우가 있으므로, 최소값으로 넣어주었다.

그리고 플로이드 와샬을 3중 for문으로 구현해줬다.

출력은 if else문을 이용해 INF가 그대로인 곳은 갈수 없는 곳이므로 0으로 출력해주었다.

import sys
input = sys.stdin.readline




V,E = map(int,input().split())
graph = [{} for _ in range(V+1)]

for _ in range(E):
    A,B,C = map(int,input().split())
    graph[A][B] = C
    graph[B][A] = C
INF = float('inf')
visited = [False]*(V+1)
distance = [INF]*(V+1)
distance[1] = 0

node_list = [(1,0)]
cnt = 1
result = 0
while cnt <V:
    node, dis = node_list.pop()
    current_min_dis = INF
    current_min_node = -1
    visited[node] = True
    for next_node in graph[node]:
        if distance[next_node] > graph[node][next_node]:
            distance[next_node] =  graph[node][next_node]

    for ind in range(1,V+1):
        if current_min_dis > distance[ind] and not visited[ind]:
            current_min_node = ind
            current_min_dis = distance[ind]
    node_list.append((current_min_node,current_min_dis))
    result += current_min_dis
    cnt += 1

print(result)

첫 풀이는 다익스트라랑 비슷한 프림 알고리즘을 이용한 풀이였다. 하지만 해당 풀이는 실행시간이 오래걸려서 또 다른 방식으로 풀었다.

import sys
import heapq

input = sys.stdin.readline
V,E = map(int,input().split())

graph = [{} for _ in range(V+1)]

for _ in range(E):
    A,B,C = map(int,input().split())
    graph[A][B] = C
    graph[B][A] = C
INF = float('inf')
distance = [INF]*(V+1)
visited = [False]*(V+1)
node_list = []
distance[1] = 0
heapq.heappush(node_list,(0,1))
result = 0
while node_list:
    key,node = heapq.heappop(node_list)
    if visited[node]:
        continue
    visited[node] = True
    result += key
    for next_node in graph[node]:
        if distance[next_node] > graph[node][next_node]:
            heapq.heappush(node_list,(graph[node][next_node],next_node))
            distance[node] = graph[node][next_node]
print(result)

두번째는 프림 알고리즘이지만, heapq를 활용한 풀이였다. 위의 방식과 똑같지만, distance가 갱신될때에만을 판단하고, 그때 node_list에 추가하는 방식이었다.

import sys

input = sys.stdin.readline
def union(A,B):
    x = find_parent(A)
    y = find_parent(B)
    if x > y:
        x,y = y,x
    make_set[y] = x

def find_parent(ind):
    if make_set[ind] == ind:
        return ind
    make_set[ind] = find_parent(make_set[ind])
    return make_set[ind]




V,E = map(int,input().split())

grpah = sorted([list(map(int,input().split())) for _ in range(E)],key=lambda x : x[2],reverse=True)

make_set = [i for i in range(V+1)]

cnt = 1 
result = 0

while cnt <V:
    p1,p2,weight = grpah.pop()
    if find_parent(p1) != find_parent(p2):
        union(p1,p2)
        result += weight
        cnt += 1

print(result)

크루스칼 알고리즘으로 푼 방식이다. 크루스칼 알고리즘이 편한사람들은 금방 푼다고하는데, 크루스칼 알고리즘에 익숙하지 못해서 시간이 오래걸렸다.

많이 실패했던것은 make_set에 저장된 parent_node로 비교를 했을때 틀렸다. find_parent 이후에, 루트노드가 바뀐 경우 make_set에 저장된 모든 parent들이 root_node로 갱신되는것이 아니기 때문에, 문제가 생겼었다.

프림 알고리즘과 크루스칼 알고리즘은 자주 쓰이므로 좀 더 익숙해져야겠다.