Coding 공부

import collections


def bfs(i):
    global N,graph,result
    stack = collections.deque()
    stack.append((i,0))
    visited = [True] * (N+1)
    visited[i] = False
    while stack:
        ind,dep = stack.popleft()
        for next_ind in graph[ind]:
            if visited[next_ind]:
                stack.append((next_ind,dep+1))
                visited[next_ind] = False
    return dep







N = int(input())
graph = [[] for _ in range(N+1)] 
while True:
    a,b = map(int,input().split())
    if a == -1 and b == -1:
        break
    graph[a].append(b)
    graph[b].append(a)


result = [50]*(N+1)
for i in range(1,N+1):
    result[i] = bfs(i)


min_list = [min(result),result.count(min(result))]
print(*min_list)
min_result = []
for i in range(1,N+1):
    if result[i] == min_list[0]:
        min_result.append(i)
print(*min_result)

 친구의 깊이를 물어보는 문제였다. 문제에서 들어오는 최대 인원이 50이므로 50으로 해놓은 상태에서 바꿨다.

그리고 깊이를 물어보는 것이기 때문에, DFS가 아닌 BFS를 이용해서 최단거리를 깊이로 생각해서 풀었다.

# 플로이드 와샬

N = int(input())
graph = [[0]+[50]*N if i!=0 else [50]*(N+1) for i in range(N+1)]
while True:
    a,b = map(int,input().split())
    if a == b == -1:
        break
    graph[a][b] = 1
    graph[b][a] = 1

for i in range(1,N+1):
    graph[i][i] = 0

for k in range(1,N+1):
    for from_node in range(1,N+1):
        for to_node in range(1,N+1):
            if graph[from_node][to_node] == 1 or graph[from_node][to_node] == 0:
                continue
            elif graph[from_node][to_node] > graph[from_node][k] + graph[k][to_node]:
                graph[from_node][to_node] = graph[from_node][k] + graph[k][to_node]


min_result = list(map(max,graph))

print(min(min_result),min_result.count(min(min_result)))
min_ind = []
for ind,val in enumerate(min_result):
    if val == min(min_result):
        min_ind.append(ind)
print(*min_ind)

플로이드 와샬 방식으로 푼 방식이다.

기본 원리는 같지만 연결을 표현한 방식이 달라졌을 뿐이다.

def dfs(i,cnt):
    global result
    visited[i] = False
    if cnt >= 5:
        result = True
        return
    for ind in graph[i]:
        if visited[ind]:
            dfs(ind,cnt+1)
    visited[i] = True


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


for _ in range(M):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [True]*N
result = False
for i in range(N):
    dfs(i,1)
    if result:
        break
print(int(result))

DFS를 해서 깊이가 4 이상이면 True를 반환해주면 되는 문제이다.

위와 같이 재귀를 해서 풀어도 되고, 

import sys
input = sys.stdin.readline
def solution():
    global N
    for dep0 in range(N):
        for dep1 in graph[dep0]:
            for dep2 in graph[dep1]:
                if dep0 == dep2:
                    continue
                for dep3 in graph[dep2]:
                    if dep3 == dep1 or dep3 == dep0:
                        continue
                    for dep4 in graph[dep3]:
                        if dep4 != dep0 and dep4 != dep1 and dep4 != dep2:
                            return 1
    return 0

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

print(solution())

깊이가 그리 깊지 않으니 하드코딩으로 분기처리를 해주어도 풀 수 있다.

N = int(input())


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

arr.sort()

start = 0
end = N-1
index_list = (arr[start],arr[end])
result = arr[end]+arr[start]

while start<end:
    temp = arr[end]+arr[start]
    if abs(result) > abs(temp):
        result = temp
        index_list = (arr[start],arr[end])
        if result == 0:
            break
    if temp >= 0:
        end -= 1
    else:
        start += 1


print(*index_list)

유명한 투 포인터 문제이다.

푸는 방법은 먼저 입력리스트를 정렬해준뒤에 0을 start로 N-1을 end로 둔다.

그리고 그 두 위치의 인덱스의 위치에 존재하는 값들의 합이 0보다 크면 end를 -1 하고 작으면 start를 +1 해준다. 그리고 그 합들이 0에 가까우면 교체해주는 방식으로 했다.

import sys
import heapq


def dijkstra(start,end,flag=True):
    global INF,N
    distance = [INF]*N
    distance[start] = 0
    node_list = []
    heapq.heappush(node_list,(0,start))
    while node_list:
        current_distance,node = heapq.heappop(node_list)
        if current_distance > distance[node]:
            continue          
        for next_node in graph[node]:
            temp_distance = current_distance + graph[node][next_node]
            if distance[next_node] > temp_distance:
                distance[next_node] = temp_distance
                heapq.heappush(node_list,(temp_distance,next_node))
    if flag and distance[end] != INF:
        stack = [(end,distance[end])]
        path_set = set()
        while stack:
            node,dis = stack.pop()
            for prev_node in parent[node]:
                if (prev_node,node) not in path_set:
                    if distance[prev_node] + graph[prev_node][node] == dis:
                        path_set.add((prev_node,node))
                        stack.append((prev_node,distance[prev_node]))
        
        for prev_node,next_node in path_set:
            del graph[prev_node][next_node]

    return distance[end]
INF = float('inf')
while True:
    N,M = map(int,sys.stdin.readline().split())
    if not N+M:
        break 
    S,D = map(int,sys.stdin.readline().split())

    distance = [[0]*N for _ in range(N)]
    graph = [{} for _ in range(N)]
    parent = [[] for _ in range(N)]
    for _ in range(M):
        U,V,P = map(int,sys.stdin.readline().split())
        graph[U][V] = P
        parent[V].append(U)
    min_distance = dijkstra(S,D)
    if min_distance == INF:
        print(-1)
    else:
        cu_distance = dijkstra(S,D,False)
        if cu_distance != min_distance:
            if cu_distance != INF:
                print(cu_distance)
            else:
                print(-1)

다익스트라 문제이다. 하지만 기존의 다익스트라와 달리, 최단경로를 찾아서 최적경로의 간선을 제거해줘야한다.

처음에, 최적경로 하나마다 삭제를 했더니, 최적경로의 간선은 다른 최적경로에서 사용을 할 수 있기 때문에 틀렸다고 나왔다.

두번째로는 시간초과의 늪에 많이 빠졌다. 처음에는 최적의 경로를 min_distance가 갱신될때마다 저장을 시켜놨더니 

시간이 초과가 되었다.

그래서 다음과 같은 로직으로 최적의 경로쌍을 찾아다

도착지점의 distance의 값을 distance[end]라 하겠다.

distance[prev_node] + graph[prev_node][end] == distance[end]을 만족하는 prev_node는 prev_node에서 end node로 오는 최단경로임을 알수 있다.

이 (prev_node,end) 쌍을 지울 집합에 추가해주고, prev_node를 stack에 넣어준다.

이 과정을 반복하면, 끝점에서부터 최단경로로 오는 간선들을 전부 찾을 수 있다.

그리고 난뒤 해당 간선들을 지우는 과정을 하면 된다.

그리고 마지막으로 다익스트라를 한번 더 한뒤 결과에 맞게 출력해주면 된다.

다익스트라는 자주 쓰지 않던 알고리즘이라 푸는데 어려웠고, 기본적으로 다익스트라는 최단경로의 길이를 출력해주는 것이기 때문에, 최단경로의 경로를 이용하기 위해서 다익스트라 과정에서 나온 결과물을 이용해야한다는 점을 배웠다.

드디어 150문제를 돌파했다.

골드4~5 문제가 60문제로 거의 반수가 낮은 난이도에 주력되어있어서, 상반기 시즌에 맞춰서 스퍼트를 올려서 골2~3 문제와 플5~골1 문제를 많이 연습 해봐야겠다.

def solution(A,B):
    result = [[0]*(len(B)+1) for _ in range(len(A)+1)]
    for i in range(1,len(A)+1):
        for j in range(1,len(B)+1):
            if A[i-1] == B[j-1]:
                result[i][j] = result[i-1][j-1] + 1

    return max(map(max,result))

A = input()
B = input()

print(solution(A,B))

LCS 문제이다. 근데 이전에 풀었던 LCS와 다른 문제였다.

기본적인 틀은 똑같다. 대신 이 문제는 연속된 문자열이어야 하기 때문에, A[i-1] != B[i-1]일때는 아무것도 해주지 않는다.

# 3020 개똥벌레

N,H = map(int,input().split())

bottom_list = [0]*H
top_list = [0]*H


for ind in range(N):
    height = int(input())
    if ind%2:
        top_list[height] += 1
    else:
        bottom_list[height] += 1

for ind in range(1,H):
    bottom_list[ind] += bottom_list[ind-1]
    top_list[ind] += top_list[ind-1] 

bottom_list.append(bottom_list[-1])
top_list.append(top_list[-1])
min_result = float('inf')
min_cnt = 0
for k in range(H):
    bottom_cnt = bottom_list[-1] - bottom_list[k]
    top_cnt = top_list[-1] - top_list[(H-1)-k]
    if bottom_cnt +top_cnt < min_result:
        min_result = bottom_cnt+top_cnt
        min_cnt = 1
    elif bottom_cnt + top_cnt == min_result:
        min_cnt += 1

print(min_result,min_cnt)

prefix sum 을 이용해서 푼 방식이다.  종유석과 석순을 구분해서 prefix_sum을 해주고, 그 다음에 상황에 맞게 최저값을 구해주면 된다.

# 3020 개똥벌레
import sys


N,H = map(int,sys.stdin.readline().split())

bottom_list = [0]*(H+1)
top_list = [0]*(H+1)

for ind in range(N):
    height = int(input())
    if ind%2:
        top_list[height] += 1
    else:
        bottom_list[H-height+1] += 1
for ind in range(H-1,0,-1):
    top_list[ind] += top_list[ind+1]


for ind in range(2,H+1):
    bottom_list[ind] += bottom_list[ind-1]

min_total = N
min_cnt = 0
for ind in range(1,H+1):
    sub_sum = bottom_list[ind] + top_list[ind]
    if sub_sum < min_total:
        min_total = sub_sum
        min_cnt = 1
    elif sub_sum == min_total:
        min_cnt += 1
print(min_total,min_cnt)

이 코드는 석순의 저장 방식을 다르게 하여, 한번에 계산이 편하게 한 방식이다.  

# 6593 상범 빌딩
from collections import deque


def printresult(flag,sec):
    if flag:
        return f'Escaped in {sec} minute(s).'
    else:
        return 'Trapped!'


while True:
    L,R,C = map(int,input().split())
    if L+R+C == 0:
        break
    building = []
    dx = [-1,1,0,0,0,0]
    dy = [0,0,-1,1,0,0]
    dz  = [0,0,0,0,-1,1]
    startpoint = []
    endpoint = []
    for ind in range(L):
        temp = []
        for x in range(R):
            input_list = list(input())
            for y,val in enumerate(input_list):
                if val == 'S':
                    startpoint = [x,y,ind]
                elif val == 'E':
                    endpoint = (x,y,ind)
            temp.append(input_list)
        building.append(temp)
        input()
    # 층,행,열
    stack = deque()
    stack.append(startpoint)
    building[startpoint[2]][startpoint[0]][startpoint[1]] = '#'
    minutes = 0
    flag = False
    while stack:
        new_stack = []
        minutes += 1
        for x,y,z in stack:
            for i in range(6):
                nx = x + dx[i]
                ny = y + dy[i]
                nz = z + dz[i]
                if 0<=nx<R and 0<=ny<C and 0<=nz<L:
                    if building[nz][nx][ny] != '#':
                        if (nx,ny,nz) == endpoint:
                            flag = True
                            break
                        else:
                            building[nz][nx][ny] = '#'
                            new_stack.append((nx,ny,nz))
        if flag:
            print(printresult(flag,minutes))
            break

        stack = new_stack[:]
    if not flag:
        print(printresult(flag,minutes))

BFS 관련 문제이다. 문제를 제대로 안 읽어서 input값을 제대로 안 받았더니 많이 틀렸던 문제이다.

일반적인 BFS를 3차원으로 바뀐것과 동일하고, range를 많이 쓰면 메모리 초과가 날 수 있으니 조심해서 풀면 되는 문제이다.