Coding 공부

import sys
 
def input():
    return sys.stdin.readline().rstrip()
def floyd():
    result = 0
    for mid in range(N):
        for start in range(N):
            for end in range(N):
                if start == end or end == mid or mid == start or start>end:continue
                if arr[start][end] == arr[start][mid] + arr[mid][end]:
                    if (start,end) in edge_list:
                        edge_list.remove((start,end))
                if arr[start][end] > arr[start][mid] + arr[mid][end]:
                    return -1
 
    for x,y in edge_list:
        result += arr[x][y]
    return result
N = int(input())
 
arr = [list(map(int,input().split())) for _ in range(N)]
edge_list = set()
for i in range(N):
    for j in range(N):
        if i ==j or i>j: continue
        edge_list.add((i,j))
 
print(floyd())

이 문제는 이해하기 어려웠던 문제였다.

이 문제를 읽어 보면 강호는 모든 쌍의 도시에 대해서 최소 이동시간을 구해놓았다고 했다.

그리고 민호는 이 표를 보고 원래 도로가 몇개 있는지를 구해보려고 한다고 적혀있다.

그러면 예제에 있는 도시 1-2, 2-3, 1-4, 3-4, 4-5, 3-5를 연결하는 도로만 있다고 가정해도,

강호가 구한 모든 쌍의 최솟값을 구할수 있다고 했다.

이 부분을 통해 유추를 해야한다.

원래는 여러 도로가 있었겠지만, 강호는 모든 쌍의 도시에 대해서 최소 이동시간을 구했기 때문에,

불 필요한 다른 도로들을 없애버린것이다.

즉 1->3 까지의 시간이 15인데 이것은 1->2 와 2->3을 더한 값과 동일하다.

1->5 또한 1->4 4->5를 더한 값과 동일하다.

즉 A라는 도시에서 B라는 도시를 갈때 A->C + C->B를 만족하는 경우가 있으면, A->B의 도로는 없어도, 동일한 시간 내에 갈 수 있으므로,

도로의 개수를 최솟값을 구할때 제외해도 된다.

이 부분을 주의해서 문제를 풀어주면 된다.

먼저 모든 도로들을 넣어주어야하는데, A->B와 B->A는 동일 하므로,

A<B를 만족하는 도로들을 먼저 edge_list에 전부 넣어준다.

그러면서 플로이드 와샬을 하면서

arr[start][end] == arr[start][mid] + arr[mid][end] 를 만족하는 경우엔, edge_list에서 그 도로를 제외 해준다.

또한 우리는 A<B인 경우만 하도록 했으므로, start> end 이거나, start or end 가 mid와 동일할때는 제외하고 검사해준다.

그리고 여기서 또 구해야하는 또 다른 경우는 불가능한 경우에 -1을 출력하는 조건이 있다.

이 조건을 만족하는 경우는 도시에서 다른 도시까지 가는 시간의 최소값이 갱신 되는 경우이다.

갱신 되었을 때에는 -1을 반환해주고, 아닌 경우에는 남은 edge_list를 통해 모든 도로의 시간의 합을 구하면 된다.

import sys
sys.setrecursionlimit(10000)
def input():
    return sys.stdin.readline().rstrip()
 
def checkFreinds(target_node,friend):
 
    for node in friend:
        if not friendly[node][target_node]:
            return False
    return True
 
def dfs(node,friend):
    global K,result
    if len(friend) == K:
        result = list(map(str,friend))
        sys.stdout.write('\n'.join(result))
        exit(0)
        return
 
    for next_node in range(node+1,N+1):
        if friend_cnt[next_node] < K-1:
            continue
        if visited[next_node]:
            continue
        if not friendly[node][next_node]:
            continue
        if not checkFreinds(next_node,friend):
            continue
        visited[next_node] = True
        dfs(next_node,friend +[next_node])
        visited[next_node] = False
 
 
 
K,N,F = map(int,input().split())
 
friendly = [[False for _ in range(N+1)] for _ in range(N+1)]
 
friend_cnt = [0 for _ in range(N+1)]
for _ in range(F):
    x,y = map(int,input().split())
    friendly[x][y] = True
    friendly[y][x] = True
    friend_cnt[x] += 1
    friend_cnt[y] += 1
 
result = []
visited = [False for _ in range(N+1)]
for num in range(1,N+1):
    if friend_cnt[num] < K-1:
        continue
    visited[num] = True
    dfs(num,[num])
    visited[num] = False
 
print(-1)

 이 문제는 N명 중 K명의 소풍을 보내는 것이다. 

단 조건이 모두가 서로 친구여야한다는 것이다.

그래서  N*N 친구의 관계를 나타내는 freiendly라는 행렬을 만들어 두었다.

서로 간에 친구관계이면 True 아니면 False가 되도록 했다.

이렇게 사전 준비 작업을 했다면, 백트래킹으로 문제를 접근하면 된다.

이 문제의 출력 조건은 만족하는 K명의 소풍을 갈수 있는 조합이 많으면 사전순으로 출력하는 것이다.

그러면 우리는 1번 학생부터 순차적으로 접근을 해서 만족을 하는 첫번째 K명의 조합이 사전 순으로 가장 빠른다는 것을 알 수 있게 된다.

여기서 재귀로 할때 주의를 해야할 것이 몇가지가 있다.

먼저. 현재 방문하는 친구의 친구 숫자가 K-1보다 작으면 자기를 포함해서 세도 K명이 안되기에 pass를 해주어야한다.

그리고, 문제의 조건 중에 소풍을 가는 친구들은 모두 친구관계 이어야한다.

그러므로, checkFriends 라는 함수를 통해 지금까지 뽑은 friend와 새로 방문한 next_node와 친구관계인지 파악을 해준다.

단 하나라도 만족하지 않으면 False를 반환해주면 된다.

그 뒤에는 DFS 처럼 백트래킹을 해주면 된다.

그리고, K를 만족하는 friend 조합이 나오면 exit로 파일을 종료하게 해준다.

import sys
from itertools import combinations
import math
def input():
    return sys.stdin.readline().rstrip()
 
 
 
N = int(input())
 
graph = [[] for _ in range(N+1)]
 
 
for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
 
d_cnt = 0
g_cnt = 0
 
 
for i in range(1,N+1):
    if len(graph[i])>=3:
        k = len(graph[i])
        cnt = math.factorial(k)/(math.factorial(3)*math.factorial(k-3))
        g_cnt += cnt
    if len(graph[i])>=2:
        for next_node in graph[i]:
            if len(graph[next_node])>=2:
                a = len(graph[i]) - 1
                b = len(graph[next_node]) - 1
                d_cnt += (a*b)
 
d_cnt//=2
 
if d_cnt > g_cnt*3:
    print('D')
elif d_cnt < g_cnt*3:
    print('G')
else:
    print('DUDUDUNGA')

ㅈ 을 그리는 방법은 해당 노드를 기준으로 자식노드가 3개이상이면 구할수 있따. 그러므로 자식노드 중 3개를 고르는 경우의 수를 더해주면 된다.

ㄷ을 그리는 방법은 다음과 같다. 서로 연결된 두 노드의 자식노드가 2개이상이어야할때이다.

왜냐하면 서로 연결이 되어 있으므로, 하나는 빼고 서로 다른 노드들의 개수를 곱해주면 된다.

import sys
 
def input():
    return sys.stdin.readline().rstrip()
 
def nC3(n):
    return (n*(n-1)*(n-2))//6
 
N = int(input())
 
graph_node_cnt = [0 for _ in range(N+1)]
edge_list = []
for _ in range(N-1):
    x,y = map(int,input().split())
    graph_node_cnt[x] += 1
    graph_node_cnt[y] += 1
    edge_list.append((x,y))
 
g_cnt = 0
d_cnt = 0
for node in range(1,N+1):
    if graph_node_cnt[node] >=3:
        g_cnt += nC3(graph_node_cnt[node])
 
for x,y in edge_list:
    if graph_node_cnt[x]>=2 and graph_node_cnt[y]>=2:
        d_cnt += (graph_node_cnt[x]-1)*(graph_node_cnt[y]-1)
 
 
if d_cnt>3*g_cnt:
    print('D')
elif d_cnt < 3*g_cnt:
    print('G')
else:
    print('DUDUDUNGA')

이건 팩토리얼 대신 사용한 것이다.

import sys
from collections import deque
def input():
    return sys.stdin.readline()
N,M = map(int,input().split())
 
sams = list(map(int,input().split()))
 
visited_set = set(sams)
 
queue = deque()
for sam in sams:
    queue.append((sam,0))
 
cnt = 0
result = 0
while queue:
    cur_node,dis = queue.popleft()
    result += dis
    cnt += 1
    if cnt == N+M:
        break
    for next_node in [cur_node+1,cur_node-1]:
        if next_node not in visited_set:
            visited_set.add(next_node)
            queue.append((next_node,dis+1))
print(result)

이 문제는 샘터를 기준으로 bfs를 하면서, 방문 표시를 해주면 되는 문제였다.

종료조건은 샘터의 개수와 집의 개수를 합친 개수가 되면 종료가 되게 하면 된다.

import sys
 
def input():
    return sys.stdin.readline().rstrip()
 
def fishing(y):
    for x in sorted(shark_dict[y].keys()):
        if shark_dict[y][x]:
            temp = shark_dict[y][x][2]
            del shark_dict[y][x]
            return temp
    return 0
R,C,M = map(int,input().split())
 
shark_dict = [{} for _ in range(C)]
for _ in range(M):
    x,y,speed,dire,size = map(int,input().split())
    x -= 1
    y -= 1
    dire -= 1
    shark_dict[y][x] = [dire,speed,size]
 
result = 0
dx = [-1,1,0,0]
dy = [0,0,1,-1]
reverse = [1,0,3,2]
for y in range(C):
    remain_cnt = 0
    move_shark_dict = [{} for _ in range(C)]
    result += fishing(y)
    for shark_y in range(C):
        for shark_x in shark_dict[shark_y]:
            dire, speed, size = shark_dict[shark_y][shark_x]
            nx = shark_x
            ny = shark_y
            if dire in [0,1]:
                for _ in range(speed):
                    nx += dx[dire]
                    if nx >= R-1 or nx <= 0:
                        dire = reverse[dire]
                        if nx >= R:
                            nx = R - 2
                        elif nx<0:
                            nx = 1
 
            else:
                for _ in range(speed):
                    ny += dy[dire]
                    if ny >= C-1 or ny <= 0:
                        dire = reverse[dire]
                        if ny >=C:
                            ny = C-2
                        elif ny<0:
                            ny = 1
            if move_shark_dict[ny].get(nx):
                if move_shark_dict[ny][nx][2] < size:
                    move_shark_dict[ny][nx] = [dire, speed, size]
            else:
                move_shark_dict[ny][nx] = [dire,speed,size]
                remain_cnt += 1
    if remain_cnt:
        shark_dict = [{} for _ in range(C)]
 
        for y in range(C):
            for x in move_shark_dict[y]:
                shark_dict[y][x] = move_shark_dict[y][x]
    else:
        break
 
print(result)

문제에서 정해준대로 구현과 시뮬레이션을 정직하게 한 방법이다.

즉 이동도 한칸 한칸씩 이동을 해서 통과는 했지만 시간은 오래 걸리는 풀이 방법이다.

import sys
def input():
    return sys.stdin.readline().rstrip()
 
def fishing(y):
    for x in sorted(shark_dict[y].keys()):
        if shark_dict[y][x]:
            temp = shark_dict[y][x][2]
            del shark_dict[y][x]
            return temp
    return 0
R,C,M = map(int,input().split())
 
shark_dict = [{} for _ in range(C)]
for _ in range(M):
    x,y,speed,dire,size = map(int,input().split())
    x -= 1
    y -= 1
    dire -= 1
    shark_dict[y][x] = [dire,speed,size]
 
result = 0
dx = [-1,1,0,0]
dy = [0,0,1,-1]
reverse = [1,0,3,2]
for y in range(C):
    remain_cnt = 0
    move_shark_dict = [{} for _ in range(C)]
    result += fishing(y)
 
    for shark_y in range(C):
        for shark_x in shark_dict[shark_y]:
            dire, speed, size = shark_dict[shark_y][shark_x]
            nx = shark_x + dx[dire]*speed
            ny = shark_y + dy[dire]*speed
            if dire in [0,1]:
                while not(0<=nx<R):
                    if nx<0:
                        nx = -nx
                        dire = reverse[dire]
                    else:
                        nx = (R-1)-(nx-(R-1))
                        dire = reverse[dire]
            else:
                while not(0<=ny<C):
                    if ny<0:
                        ny = -ny
                        dire = reverse[dire]
                    else:
                        ny = (C-1)-(ny-(C-1))
                        dire = reverse[dire]
 
            if move_shark_dict[ny].get(nx):
                if move_shark_dict[ny][nx][2] < size:
                    move_shark_dict[ny][nx] = [dire, speed, size]
            else:
                move_shark_dict[ny][nx] = [dire,speed,size]
                remain_cnt += 1
    if remain_cnt:
        shark_dict = [{} for _ in range(C)]
 
        for y in range(C):
            for x in move_shark_dict[y]:
                shark_dict[y][x] = move_shark_dict[y][x]
    else:
        break
 
print(result)

두번째 풀이는 방향을 한번에 구하는 것을 통해 시간을 아낄수 있었다. 정확히 말하면 한번은 아니지만, 한칸한칸씩 움직이는 것보다 빠르게 만들었다.

import sys
def input():
    return sys.stdin.readline().rstrip()
 
def fishing(y):
    for x in range(R):
        if pos[x][y]:
            size = sharks[pos[x][y]][4]
            del sharks[pos[x][y]]
            pos[x][y] = 0
            return size
    return 0
R,C,M = map(int,input().split())
 
sharks = {}
 
pos = [[0 for _ in range(C)] for _ in range(R)]
for num in range(1,M+1):
    x,y,speed,dire,size = map(int,input().split())
    x -= 1
    y -= 1
    dire -= 1
    sharks[num] = (x,y,speed,dire,size)
    pos[x][y] = num
 
 
result = 0
dx = [-1,1,0,0]
dy = [0,0,1,-1]
reverse = [1,0,3,2]
for y in range(C):
    if len(sharks)==0:
        break
    result += fishing(y)
    next_pos = [[0 for _ in range(C)] for _ in range(R)]
    eaten = []
    for num in sharks:
        shark_x,shark_y,speed,dire,size = sharks[num]
        nx = shark_x + dx[dire]*speed
        ny = shark_y + dy[dire]*speed
        if dire in [0,1]:
            while not(0<=nx<R):
                if nx<0:
                    nx = -nx
                    dire = reverse[dire]
                else:
                    nx = (R-1)-(nx-(R-1))
                    dire = reverse[dire]
        else:
            while not(0<=ny<C):
                if ny<0:
                    ny = -ny
                    dire = reverse[dire]
                else:
                    ny = (C-1)-(ny-(C-1))
                    dire = reverse[dire]
 
 
        if next_pos[nx][ny] != 0:
            prev_shark_num = next_pos[nx][ny]
            if sharks[prev_shark_num][4] < size:
                next_pos[nx][ny] = num
                sharks[num] = (nx,ny,speed,dire,size)
                eaten.append(prev_shark_num)
            else:
                eaten.append(num)
 
        else:
            next_pos[nx][ny] = num
            sharks[num] =  (nx,ny,speed,dire,size)
    for num in eaten:
        del sharks[num]
    pos = [row[:] for row in next_pos]
 
print(result)

이 풀이는 상어의 정보를 저장하는 딕셔너리와 상어의 위치를 알 수 있는 리스트를 통해 관리를 해서 푸는 방식이다.

import sys
 
def input():
    return sys.stdin.readline()
 
N,M = map(int,input().split())
 
def find_parents(X):
    if X == make_set[X]:
        return X
    make_set[X] = find_parents(make_set[X])
    return make_set[X]
 
 
def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)
 
    if X !=Y:
        if ranks[X]< ranks[Y]:
            X,Y = Y,X
        make_set[Y] = X
        cnt[X] += cnt[Y]
        if ranks[X] == ranks[Y]:
            ranks[X] += 1
        return True
    return False
dire = {
    "U": [-1,0],
    "L": [0,-1],
    "R" : [0, 1],
    'D': [1,0]
}
 
arr = [list(input()) for _ in range(N)]
make_set = [i for i in range(N*M+1)]
ranks = [1 for _ in range(N*M+1)]
cnt = [1 for _ in range(N*M+1)]
ranks[N*M] = float('inf')
 
for x in range(N):
    for y in range(M):
        point = x*M+y
        dx,dy = dire[arr[x][y]]
        nx = x + dx
        ny = y + dy
 
        if 0<=nx<N and 0<=ny<M:
            next_point = (x+dx)*M+y+dy
            union(point,next_point)
        else:
            union(point,N*M)
print(cnt[N*M]-1)

boj.kr/16724 와 동일한 방식으로 풀었다.

그러니깐 미로를 탈출 즉 범위를 벗어나는 경우를 N*M일때로 지정을 해주고, ranks를 최대로 준뒤

무조건 외각이 되었을때 외각이 부모가 되도록 만들어줬다.

주어진 미로의 크기는 N*M인데, N*M + 1 만큼의 make_set과 ranks, cnt를 만들어주고,

미로의 범위 내 이면 두개의 점을 union을 해주고,

범위 밖이면 우리가 만들어놓은 N*M에 union을 해주게 했다.

그리고 마지막에 cnt[N*M]에서 -1을 해주면 전체에서 탈출할 수 있는 칸의 수가 나오게 된다.

import sys
 
def input():
    return sys.stdin.readline().rstrip()
def find_parents(X):
    if X == make_set[X]:
        return X
    make_set[X] = find_parents(make_set[X])
    return make_set[X]
def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)
    if X !=Y:
        if ranks[X] < ranks[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if ranks[X] == ranks[Y]:
            ranks[X] += 1
        return True
 
def connect(r1,r2):
    if (r1['x1'] > r2['x1'] and r1['y1'] > r2['y1']   and r1['x2'] < r2['x2']  and r1['y2'] < r2['y2']):
        return False
    if (r1['x1'] < r2['x1'] and r1['y1'] < r2['y1']   and r1['x2'] > r2['x2']  and r1['y2'] > r2['y2']):
        return False
    if (r2['x1'] > r1['x2'] or r2['x2'] < r1['x1'] or r2['y1'] > r1['y2'] or r2['y2'] < r1['y1']):
        return False
    return True
N = int(input())
 
rect = [{
        'x1' : 0,
        'x2' : 0,
        'y1' : 0,
        'y2' : 0
    }]
for _ in range(N):
    x1,y1,x2,y2 = map(int,input().split())
    rect.append({
        'x1' : x1,
        'x2' : x2,
        'y1' : y1,
        'y2' : y2
    })
make_set = [i for i in range(N+1)]
ranks = [1 for _ in range(N+1)]
 
 
for i in range(N+1):
    for j in range(N+1):
        if i != j and connect(rect[i],rect[j]):
            if find_parents(i) != find_parents(j):
                union(i,j)
 
 
for ind in range(N):
    find_parents(ind)
 
 
print(len(set(make_set))-1)

어려웠던 문제였다. 이 문제를 푸는 방법은 사각형끼리 겹쳐있는지 아닌지를 판별을 해주고, 안 겹친 사각형이 총 몇개인지 세면 되는 문제였다.

단 거북이는 0,0 부터 시작하므로 0,0,0,0 으로 된 사각형이 있다고 가정하에 union find를 진행해주면 되는 문제였다.

import sys
def input():
    return sys.stdin.readline().rstrip()
N,M,R = map(int,input().split())
arr = [0] + list(map(int,input().split()))
 
graph = [{} for _ in range(N+1)]
 
 
INF = float('inf')
distance = [[0 if i == j else INF for j in range(N+1)] for i in range(N+1)]
for _ in range(R):
    x,y,pay = map(int,input().split())
    graph[x][y] = min(graph[x].get(y,float('inf')), pay)
    graph[y][x] = min(graph[y].get(x, float('inf')),pay)
    distance[x][y] = min(distance[x][y],pay)
    distance[y][x] = min(distance[y][x],pay)
 
value = [0 for _ in range(N+1)]
for mid in range(1,N+1):
    for start in range(1,N+1):
        for end in range(1,N+1):
            if distance[start][end] > distance[start][mid] + distance[mid][end]:
                distance[start][end] =  distance[start][mid] + distance[mid][end]
 
 
result = 0
for node in range(1,N+1):
    temp = 0
    for next_node in range(1,N+1):
        if distance[node][next_node] <= M:
            temp += arr[next_node]
    if temp > result:
        result = temp
print(result)

이 문제는 플로이드와샬을 통해 최단거리를 갱신해주고, 

N^2를 탐색하면서, 거리가 M 이하일때 더해줘서 최대값을 갱신해서 출력해주는 문제이다.