Coding 공부

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

# 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)