Coding 공부

import math

def find_num(N):
    x1, y1, r1, x2, y2, r2 = map(int, N.split(' '))
    
    dist = math.sqrt((x1-x2)**2 + (y1-y2)**2)
    
    if(dist == 0):
        if(r1 == r2):
            print('-1')
        else:
            print('0')
    else:        
        if(dist < r1+r2):
            if (dist + min(r1, r2)) == max(r1, r2):
                print(1)
            elif (dist + min(r1, r2) < max(r1, r2)):
                print(0)
            else:
                print(2)
        elif(dist == r1+r2):
            print('1')
        else:
            print('0')

n = int(input())

for i in range(0, n):
    N = input()
    find_num(N)

이 문제는 수학을 이용해서, 각 거리에 따라, 어느위치에 존재하는지 확인해서 출력해주면 된다.

# 5014 스타트링크
# F층 건물 스타트링크 있는 위치 G 강호가있는 층은 S
# U,D
import collections
def bfs(start,end,up,down):
    global F
    visited[start] = 1
    deque = collections.deque()
    deque.append((start,0))
    dx = [up,-down]
    result = 'use the stairs'
    while deque:
        num,cnt = deque.popleft()
        if num == end:
            result = cnt
            break
        for i in range(2):
            nx = num + dx[i]
            if 0 <= nx <= F:
                if not visited[nx]:
                    visited[nx] = 1
                    deque.append((nx,cnt+1))
    return result


F,S,G,U,D = map(int,input().split())
visited = [0]*(F+1)
visited[0] = 1

print(bfs(S,G,U,D))

기본 원리는 BFS를 이용해서, 최단 이동거리를 이용하는거와 같다. 가장 가까이 갈수 있는 경우를 구하는 것이므로 BFS를 썼다.

여기서 주의해야할 점은 F+1 크기만큼의 viisted의 함수를 만들어주고, deque가 전부 비면, 갈수 있는 방안이 없는걸로 판단해야한다.

def check(cnt,total,di):
    global result
    if cnt == arr[0]:
        temp = 1
        for k in di:
            temp *= arr[dire.index(k)+1]/100
        result += temp
        return
    else:
        cu_x,cu_y = total[-1]
        for i in range(4):
            nx = cu_x + dx[i]
            ny = cu_y + dy[i]
            if (nx,ny) not in total:
                check(cnt+1,total+[(nx,ny)],di+[dire[i]])
    


# 동 서 남 북
dx = [0,0,1,-1]
dy = [1,-1,0,0]
dire = ['E','W','S','N']
arr = list(map(int,input().split()))
result = 0
check(0,[(0,0)],[])
print(ccnt)

기본적인 재귀함수를 통해 탐색을 통해 구할 수 있다. 중복이 있으면 재귀를 실행안해주고, 끝까지 갈때까지 해주는 것이다.

이 방법은 되는 것을 구하는 방식인데, 끝까지 가야하므로, 실행시간이 오래걸린다.

def dfs(x,y,persent,cnt):
    global revers_persen,N,total
    if arr[x][y] == 1:
        revers_persen += persent
        return
    if cnt == N:
        return
    arr[x][y] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if persentlist[i]:
            dfs(nx,ny,persent*persentlist[i],cnt+1)
    arr[x][y] = 0



N,e,w,s,n = map(int,input().split())

e,w,s,n = e/100,w/100,s/100,n/100
dx = [0,0,1,-1]
dy = [1,-1,0,0]
persentlist = [e,w,s,n]
arr = [[0]*29 for _ in range(29)]

revers_persen = 0
dfs(14,14,1,0)
print(f'{1-revers_persen:.10f}')

이 방법은 역으로 되지 않는 경우의 확률을 구해서, 1에서 빼주는 것이다. 이때는, format을 통해 소숫점 자리수까지 나오게 해줘야한다.

def checkheight(alp):
    if alp.isupper():
        return ord(alp) - ord('A')
    else:
        return ord(alp)-ord('a')+26

def custom_minus(a,b,flag):
    if flag:
        return a - b
    else:
        return b - a

def solve(timeslist,flag):
    global N,M,T
    dx = [-1,1,0,0]
    dy = [0,0,1,-1]
    total = 0
    visited = [[True] * M for _ in range(N)]
    x = 0
    y = 0
    timeslist[0][0] = 0
    while total <N*M:
        visited[x][y] = False
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx< N and 0 <= ny <M:
                gap = custom_minus(arr[x][y],arr[nx][ny],flag)
                if abs(gap) <= T:
                    if gap < 0:
                        time_temp = abs(gap)**2
                        
                    else:
                        time_temp = 1
                    timeslist[nx][ny] = min(timeslist[nx][ny],timeslist[x][y]+time_temp)
        next_node_x = -1
        next_node_y = -1
        next_times = INF
        for i in range(N):
            for j in range(M):
                if visited[i][j] and next_times > timeslist[i][j]:
                    next_times = timeslist[i][j]
                    next_node_x = i
                    next_node_y = j
        x = next_node_x
        y = next_node_y
        total += 1
        if next_times == INF:
            break

        



N,M,T,D = map(int,input().split())
arr = [list(map(checkheight,list(input()))) for _ in range(N)]
INF =float('inf')

times = [[INF]*M for _ in range(N)]
reversed_times = [[INF]*M for _ in range(N)]
solve(times,True)
solve(reversed_times,False)
max_height = arr[0][0]

for i in range(N):
    for j in range(M):
        if times[i][j] + reversed_times[i][j] <= D and max_height < arr[i][j]:
            max_height = arr[i][j]
print(max_height)

이 문제는 다익스트라 알고리즘을 이용해서 푼 문제이다.

ord라는 함수를 통해, 알파벳을 문제에 주어진 숫자로 변경시켜주었다.

이 문제는 처음에 냈을때 틀렸는데, 그 이유는, 문제를 제대로 읽지 않고, 해당 목적지까지 정해진 시간 D 까지만 가면 되는 줄 알았는데, 처음 호텔위치로 돌아와야했다.

이 문제는 단순히 다익스트라를 두번 돌리면 된다.

출발지와 목적지까지 올라가는 다익스트라 한번

목적지에서 출발지로 돌아오는 다익스트라 한번

하면된다.

이 문제를 두개의 함수로 나뉘어서 하기 싫어서 flag라는 변경점을 주고, 하산할때에는 뺄셈 방식을 반대로 해주게 하여, 하나의 다익스트라를 찾는 함수로 올라갈때와 내려갈때를 구현했다.

그리고 문제를 풀고난뒤, 다른사람들 풀이를 보니, 전체 N이 작아서 플로이드 와샬 방법으로 풀어도 된다고 한다.

하지만, 플로이드 와샬이 아직 잘 몰라서 그 방법으로 못 풀어봤다.

나중에 기회가 되면 플로이드 와샬로도 풀어볼 예정이다.

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를 돌려서 이어진 뿌요를 찾고, 그 뿌요가 하나도 없으면 멈추면 된다.