Coding 공부

N = int(input())
M = int(input())
graph ={i:[] for i in range(N+1)}
for i in range(M):
    node_x,node_y,fee = map(int,input().split())
    graph[node_x].append((node_y,fee))

start,end = map(int,input().split())
INFS = float('inf')
min_fees = [INFS] *(N+1)
visted = [0]*(N+1)
min_fees[start] = 0
visted[start] = 1
result = 0
node = start
while node != end:
    visted[node] = 1
    for next_node,fee in graph[node]:
        min_fees[next_node] = min(min_fees[next_node],min_fees[node]+fee)

    next_min_fees = INFS
    next_min_nodes = -1
    for ind in range(N+1):
        if not visted[ind] and next_min_fees > min_fees[ind]:
            next_min_fees = min_fees[ind]
            next_min_nodes = ind
    node = next_min_nodes


print(min_fees[end])

다익스트라 알고리즘을 이용한 문제이다.

heapq를 사용하지 않는 방식으로,

목적지로 생각되는 end가 나올때까지 반복을 하는것이다.

기본 원리는 다음과 같다.

노드와 같은 개수의 비용 리스트와 방문 리스트를 만들어준다.

그리고 비용 리스트는 무한대(큰 수)로 초기화 해주고, 출발지만 0으로 만들어준다.

방문리스트도 출발지만 방문표시로 바꿔준다.

그리고 난뒤에 출발지 노드와 인접한 노드들의 비용을 갱신해준다.

그리고 전체 노드를 돌아보면서, 방문하지 않았고, 최소비용인 노드를 다음노드로 선택해준다.

위와 같은 방식을 계속 반복해주면 된다.

import sys
import heapq

input = sys.stdin.readline

N = int(input())
M = int(input())
graph =[[] for i in range(N+1)]
for i in range(M):
    node_x,node_y,fee = map(int,input().split())
    graph[node_x].append((node_y,fee))

start,end = map(int,input().split())
INFS = float('inf')
min_fees = [INFS] *(N+1)
node_list = []
heapq.heappush(node_list,(0,start))
min_fees[start] = 0
while node_list:
    cu_distance, node = heapq.heappop(node_list)
    if min_fees[node] < cu_distance:
        continue
    for next_node,fee in graph[node]:
        if fee + cu_distance < min_fees[next_node]:
            min_fees[next_node] = fee + cu_distance
            heapq.heappush(node_list,(min_fees[next_node],next_node))
print(min_fees[end])

heapq를 이용한 풀이방식이다.

import itertools
import collections

def bfs(arr,team):
    q=collections.deque()
    q.append(arr)
    cnt=1
    visited[arr]=True
    while q:
        node=q.popleft()
        for k in graph[node]:
            if visited[k]==False and k in team:
                visited[k]=True
                q.append(k)
                cnt+=1
    if cnt==len(team):
        return True
    else:
        return False
 

N=int(input())
arr=list(range(1,N+1))
people=[0]

people.extend(list(map(int,input().split())))
graph=[[]]
people_total=sum(people)
for i in range(N):
    temp=list(map(int,input().split()))
    graph.append(temp[1:])
min_number=999999999999999
for i in range(1,N//2+1):
    b=itertools.combinations(arr,i)
    for k in b:
        a_team=list(k)
        b_team=list(set(arr)-set(k))
        
        visited=[False]*(N+1)
        
        if bfs(a_team[0],a_team) and bfs(b_team[0],b_team):        
            a_team_sum=0
            for tt in a_team:
                a_team_sum+=people[tt]
            b_team_sum=people_total-a_team_sum
            if abs(b_team_sum-a_team_sum)<=min_number:
                min_number=abs(b_team_sum-a_team_sum)       
    if min_number==0:
        break
if min_number>1000:
    print(-1)
else:
    print(min_number)

기본적인 그래프 이론이다.

기본 컨셉은 combination을 이용해 전체 N에서 절반만큼만 구한다. 이유는 조합은 n-k 와 k일떄의 조합은 같기 때문이다.

그렇게 구한 조합에서 set을 이용해서 서로 뺄샘으로 a_team과 b_team을 구하고, 경로탐색을 통해 서로 이어진 숫자와 팀의 길이와 같은지 구분을 하고, 게리멘더링이 성립되는경우에 두 팀간의 격차를 구하고, 최소값을 갱신해준다.

def dfs(x,y,value,cnt):
    global N,M,max_value
    if cnt == 4:
        if max_value < value:
            max_value = value
        return 
    else:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx <N and 0<= ny <M:
                if visted[nx][ny] == 0:
                    visted[nx][ny] = 1
                    dfs(nx,ny,value+arr[nx][ny],cnt+1)
                    visted[nx][ny] = 0


def check(x,y):
    global N,M,max_value
    another_matrix = [[[0,-1],[0,0],[0,1],[1,0]],
    [[0,-1],[0,0],[0,1],[-1,0]],
    [[-1,0],[1,0],[0,0],[0,1]],
    [[-1,0],[1,0],[0,0],[0,-1]]]
    for tus in another_matrix:
        flag = True
        temp = 0
        for cx,cy in tus:
            nx = x + cx
            ny = y + cy
            if 0<= nx <N and 0<= ny<M:
                temp += arr[nx][ny]
            else:
                flag = False
                break
        if flag:
            if max_value < temp:
                max_value = temp
N,M = map(int,input().split())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
arr = [list(map(int,input().split())) for _ in range(N)]
visted = [[0]*M for _ in range(N)]
max_value = 0
for x in range(N):
    for y in range(M):
        visted[x][y] = 1
        dfs(x,y,arr[x][y],1)
        visted[x][y] = 0
        check(x,y)


print(max_value)

BFS가 아니라 DFS를 이용해서 해야한다. DFS를 이용해서 하면, ㅗ 모양을 제외하고는 전부 추적이 가능하다.

그 부분만 따로 검증하면 된다. 길이가 3일때 검증하면 된다.

import sys
def dfs(x,y,result,total):
    global N,M,max_value
    if visited[x][y]:
        return
    if len(total) == 4:
        if max_value < result:
            max_value = result
        return
    visited[x][y] = 1
    for i in range(3):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<= nx < N and 0 <= ny <M:
            if not visited[nx][ny]:
                dfs(nx,ny,result+arr[nx][ny],total+[(nx,ny)])
    if len(total) == 3:
        center_x,center_y = total[1]
        for i in range(4):
            nx = center_x + dx[i]
            ny = center_y + dy[i]
            if 0<= nx < N and 0 <=ny<M:
                if not visited[nx][ny]:
                    dfs(nx,ny,result+arr[nx][ny],total+[(nx,ny)])
    visited[x][y] = 0
    return



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

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


arr = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
visited = [[0]*M for _ in range(N)]
max_value = 0
for x in range(N):
    for y in range(M):
        dfs(x,y,arr[x][y],[(x,y)])
print(max_value)

이게 좀 더 깔끔한 코드이다.

def bfs(x,y,color):
    global puyo,visited,arr
    temp = [[x,y]]
    stack = [[x,y]]
    while stack:
        sx,sy = stack.pop(0)
        for i in range(4):
            nx = sx + dx[i]
            ny = sy + dy[i]
            if 0<= nx < 12 and 0 <= ny <6:
                if arr[nx][ny] == color and visited[nx][ny]:
                    visited[nx][ny] = 0
                    stack.append([nx,ny])
                    temp.append([nx,ny])
    if len(temp) >= 4:
        return temp
    else:
        return []




arr = [list(input()) for _ in range(12)]
times = 0
dx = [-1,1,0,0]
dy = [0,0,-1,1]
while True:
    visited= [[1]*6 for _ in range(12)]
    puyo = []
    for x in range(12):
        for y in range(6):
            if arr[x][y] != '.' and visited[x][y]:
                visited[x][y] = 0
                check = bfs(x,y,arr[x][y])
                if check:
                    for x,y in check:
                        puyo.append((x,y))
    for x,y in puyo:
        arr[x][y] = '.'
    if len(puyo) == 0:
        break
    new_arr = [['.']*6 for _ in range(12)]
    for y in range(6):
        temp = []
        for x in range(11,-1,-1):
            if arr[x][y] != '.':
                temp.append(arr[x][y])
        for i in range(len(temp)):
            new_arr[11-i][y] = temp[i]
    arr = [row[:] for row in new_arr]
    times += 1
print(times)

 이 문제는 한단계씩 BFS를 돌려서 이어진 뿌요를 찾고, 그 뿌요가 하나도 없으면 멈추면 된다.

# R,C 비어있는곳 . 물이 차있는 * 비버의 굴 d 고슴도치S 돌은 X



R,C = map(int,input().split())

arr = [list(input()) for _ in range(R)]
gos = []
end = []
water = []
visited = [[1] * C for _ in range(R)]
for x in range(R):
    for y in range(C):
        if arr[x][y] != '.' and arr[x][y] != 'X':
            if arr[x][y] == 'S':
                gos.append((x,y,0))
                visited[x][y] = 0
            elif arr[x][y] == 'D':
                end.extend((x,y))
            else:
                water.append((x,y))
dx = [-1,1,0,0]
dy = [0,0,-1,1]
flag = False
water_time = - 1
while gos:
    x,y,time = gos.pop(0)
    if x == end[0] and y == end[1]:
        result = time
        flag = True
        break
    if water_time < time:
        new_water = []
        for wx,wy in water:
            for i in range(4):
                wnx = wx + dx[i]
                wny = wy + dy[i]
                if 0<= wnx <R and 0<= wny <C:
                    if arr[wnx][wny] == '.':
                        new_water.append((wnx,wny))
                        arr[wnx][wny] = '*'
        water_time += 1
        water = [row[:] for row in new_water]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<= nx < R and 0<= ny < C and visited[nx][ny]:
            if arr[nx][ny] == '.' or arr[nx][ny] == 'D':
                visited[nx][ny] = 0
                if nx == end[0] and ny == end[1]:
                    flag = True
                    result = time + 1
                    break
                gos.append((nx,ny,time+1))
    if flag:
        break
if flag:
    print(result)
else:
    print('KAKTUS')

BFS를 이용해서 문제를 푸는데 한가지만 조심해주면 된다. 물은 한번만 차오르고, 같은시간대에 고슴도치는 여러군데에 들릴수도 있으니, 물이 차오르는 특수조건을 주고, 그때에만 물이 번지는걸 유의해주면 된다.

import collections
N = int(input())
arr = list(map(int,input().split()))
a = collections.Counter(arr)
if max(a.values()) > 2 or  len(a.keys()) != max(a.keys())+1:
    print(0)
else:
    keys = sorted(a.keys())
    result = 1
    prev_cnt = a[0]
    flag = True
    onecnt = False
    for k in keys:

        if prev_cnt < a[k]:
            flag = False
            break
        else:
            prev_cnt = a[k]
            if a[k] == 2:
                result*=2
            else:
                onecnt = True
    if flag:
        if onecnt:
            print(result*2)
        else:    
            print(result)
    else:
        print(0)

이 문제는 경우의 수를 구해주면 된다. 

이 문제에서 중요한 것은, 연속되는 숫자들만 존재해야하고, 같은 숫자는 3개 이상이 되지 않으며,

뒤의 숫자의 개수가 앞의 숫자보다 많으면 안된다.

그리고 2개씩 존재하는 수의 개수만큼 2의 제곱승이 되고, 2개씩 존재하는 수 외에 1개씩 존재하는 수가 있으면, 2배를 해주면된다.

이 부분만 캐치해주면 코드로 구현해주면 된다.

위의 풀이는 조금 난잡하게 된 코드이다.

좀 더 깔끔한 코드는 밑에 올린다.

total = [0]*41
n = int(input())
arr = list(map(int,input().split()))
for num in arr:
    total[num] += 1
prev_cnt = 2
flag = False
for cnt in total:
    if cnt > prev_cnt:
        flag = True
        break
    prev_cnt = cnt

if flag:
    print(0)
else:
    result = 2**(total.count(2) + (1 in total))
    print(result)

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

def bfs(x,y,number):
    q=collections.deque()
    q.append([x,y])
    visited[x][y]=1
    arr[x][y]=number
    while q:
        ax,ay=q.popleft()
        for i in range(4):
            nx=ax+dx[i]
            ny=ay+dy[i]
            if 0<=nx<N and 0<=ny<M:
                if arr[nx][ny]==1 and visited[nx][ny]==0:
                    q.append([nx,ny])
                    arr[nx][ny]=number
                    visited[nx][ny]=1

def find_min_distance(land_number):
    dist=[[-1]*M for _ in range(N)]
    q=collections.deque()
    for i in range(N):
        for j in range(M):
            if arr[i][j]==land_number:
                dist[i][j]=0
                q.append([i,j])

    while q:
        x,y=q.popleft()

        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<N and 0<=ny<M:
                if dist[nx][ny]:
                    distance=1
                    while True:
                        nx=nx+dx[i]
                        ny=ny+dy[i]
                        if nx<0 or nx>=N or ny<0 or ny>=M:
                            break
                        if dist[nx][ny]==0:
                            break
                        if 0<=nx<N and 0<=ny<M:
                            if arr[nx][ny]>0 and arr[nx][ny]!=land_number:
                                if distance>1:
                         
                                    min_distance[arr[nx][ny]][land_number]=min(min_distance[arr[nx][ny]][land_number],distance)
                                    min_distance[land_number][arr[nx][ny]]=min(min_distance[land_number][arr[nx][ny]],distance)
                                break
                        
                        
                        distance+=1





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

island=1
arr=[list(map(int,input().split())) for i in range(N)]
visited=[[0]*M for i in range(N)]
for i in range(N):
    for j in range(M):
        if arr[i][j]==1 and visited[i][j]==0:
            bfs(i,j,island)
            island+=1

min_distance=[[99999]*(island) for _ in range(island)]
for i in range(1,island):
    find_min_distance(i)

total_list=[]
for i in range(island):
    for j in range(island):
        if min_distance[i][j]!=99999:
            total_list.append([i,j,min_distance[i][j]])
total_list.sort(key= lambda x : x[2])

conneted_list=[0]*island
conneted_list[0]=1
conneted_list[1]=1

result=0
while sum(conneted_list)!=island:
    for total in total_list:
        start =total[0]
        end = total[1]
        value=total[2]
        if conneted_list[start] or conneted_list[end]:
            if conneted_list[start] and conneted_list[end]:
                continue
            else:
                conneted_list[start]=1
                conneted_list[end]=1
                result+=value
                break
    else:
        result=-1
        break

print(result)

 MST 알고리즘 문제이다. 이 문제가 mst라는지도 모르고 풀었었다.

각각의 섬들의 최소 거리들을 구해주고, 그것을 짧은거리를 기준으로 정렬을 해준다.

두 섬중 하나라도 연결되어 있어야하고, 만약 둘다 연결이 되어있는 상태면 이미 연결한 것이므로, 다음으로 넘어가고, 둘중 하나만 연결되어 있을 때, 다리를 놓아주고 그 값을 결과값에 더해준다. 그리고 다시 처음부터 시작해준다.

그리고 만약 break를 한번도 마주치지 않고, 반복문이 끝난거면 더 이상 연결될 섬이 없는 경우이므로 -1을 출력해주면 된다.

from collections import deque

def bfs(x):
    queue = deque()
    queue.append(x)
    distance[x] = 0
    while queue:
        now = queue.popleft()
        for next_node in graph[now]:
            if visited[next_node] == False:
                visited[next_node] = True
                if distance[next_node] == -1:
                    distance[next_node] = distance[now] + 1
                    queue.append(next_node)
                
                

n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)

distance = [-1] * (n + 1)
visited = [False] * (n + 1)

bfs(x)

result = []
check = False
for i in range(1, n + 1):
    if distance[i] == k:
        result.append(i)
        check = True
if len(result):
    for i in range(len(result)):
        print(result[i])
else:
    print(-1)

 기초적인 다익스트라 문제이고, 다익스트라를 모르더라도 BFS를 아는 것만으로 풀 수 있다.

이 문제를 풀 시기에 다익스트라를 몰랐고, 현재도 다익스트라를 배웠지만 자주 안 쓰다보니 까먹었다!(다시 공부해야한다.)

이 문제는 단 방향 그래프이고, 방문 여부와 거리를 저장하기 위한 리스트를 만들어주었다.

bfs 를 통해 현재 위치에서 최단거리를 구하고, 이동거리를 저장하고 주어진 K와 같은 노드들을 출력해주면 된다.