내 인생 이대로 ㅈ될 수 없다

https://www.acmicpc.net/problem/1238

내 풀이

시도1

def solution():
    INF = int(1e9)
    n,m,x=map(int,input().split())
    time_list=[]
    result=[[]]
    
    graph = [[] for _ in range(m+1)]
    
    for _ in range(m):
        a,b,c= map(int,input().split())
        graph[a].append((b,c))
      
    def get_smallest_node():
        min_value = INF
        index = 0
        for i in range(1, n+1):
            if distance[i] < min_value and not visited[i]:
                min_value = distance[i]
                index = i
        return index
    def ekdlrtmxmfk(start):
        distance[start]=0
        visited[start]=1
        
        for j in graph[start]:
            distance[j[0]]=j[1]
        for _ in range(n-1):
            now = get_smallest_node()
            visited[now] = True
        
            for j in graph[now]:      
                cost = distance[now] + j[1]

                if cost<distance[j[0]]:
                    distance[j[0]] = cost
        return distance
    for i in range(1,n+1):
        distance = [INF] * (n+1)
        visited = [0] * (n+1)
        result.append(ekdlrtmxmfk(i))

    for i in range(1, n+1):
        time_list.append(result[i][x] + result[x][i])
    
    print(max(time_list))

시간초과가 났다. 특정 한 점에서 다른 모든점까지의 거리를 구하는 부분에서 다익스트라는것을 알았지만 단 한번도 다익스트라 문제를 풀면서 heapq를 사용하지 않은적이 없어서 문득 그냥 구현하면 통과가 될까싶어 한번해보았다.

시도2

import sys
import heapq

input = sys.stdin.readline
INF = int(1e9)


def solution():
    n,m,x = map(int,input().split())
    graph =[[] for _ in range(n+1)]

    for _ in range(m):
        a,b,c = map(int,input().split())
        graph[a].append((b,c))
    
    def ekdlrtmxmfk(start):
        q = []
        heapq.heappush(q,(0,start))
        distance[start] = 0

        while q:
            dist,now = heapq.heappop(q)
            
            for i in graph[now]:
                cost = dist + i[1]
                if cost < distance[i[0]]:
                    distance[i[0]]=cost
                    heapq.heappush(q,(cost,i[0]))
        return distance
    
    result = [[]]
    dis =[]

    for i in range(1,n+1):
        distance= [INF] * (n+1)
        result.append(ekdlrtmxmfk(i))
    for i in range(1,n+1):
        dis.append(result[i][x]+result[x][i])
    print(max(dis))
    

solution()

원리는 같은데 heapq를 사용한 방법이다. 

다른사람의 풀이

최근에 기사시험을 시작으로 본격적인 취준이 시작되었다. 아직 한학기가 남긴했지만 지원가능한 회사에 꽤나 많이 지원했는데(다행히도 서류는 꽤 많이 붙었다) 저번주부터 코딩테스트가 시작되었다. 18학점을 들어야하는 상황이라 학교 중간고사도 겹치다보니 쉽지않다..

하루에 하나정도는 문제를 꼭 풀어야겠다 + sql도

https://www.acmicpc.net/problem/1389

내 풀이

import sys
from collections import deque

input = sys.stdin.readline

def solution():
    ans=[]
    
    n,m = map(int,input().split())
    graph=[[] for _ in range(n+1)]
    for _ in range(m):
        a, b = map(int,input().split())
        graph[a].append(b)
        graph[b].append(a)
    
    def bfs(v):
        q = deque([v])
        visited[v]=1
        print('q=',q)

        while q:
            node = q.popleft()
            print('node=',node)

            for i in graph[node]:
                print('i=',i)
                if not visited[i]:
                    visited[i] = visited[node] + 1
                    q.append(i)
        print('visited=',visited)

    for i in range(1,n+1):
        visited=[0]*(n+1)
        bfs(i)
        ans.append(sum(visited))

    for i in range(len(ans)):
        if ans[i]==min(ans):
            print(i+1)
            return

solution()

5 5
1 3
1 4
4 5
4 3
3 2
q= deque([1])
node= 1
i= 3
i= 4
node= 3
i= 1
i= 4
i= 2
node= 4
i= 1
i= 5
i= 3
node= 2
i= 3
node= 5
i= 4
visited= [0, 1, 3, 2, 2, 3]
q= deque([2])
node= 2
i= 3
node= 3
i= 1
i= 4
i= 2
node= 1
i= 3
i= 4
node= 4
i= 1
i= 5
i= 3
node= 5
i= 4
visited= [0, 3, 1, 2, 3, 4]
q= deque([3])
node= 3
i= 1
i= 4
i= 2
node= 1
i= 3
i= 4
node= 4
i= 1
i= 5
i= 3
node= 2
i= 3
node= 5
i= 4
visited= [0, 2, 2, 1, 2, 3]
q= deque([4])
node= 4
i= 1
i= 5
i= 3
node= 1
i= 3
i= 4
node= 5
i= 4
node= 3
i= 1
i= 4
i= 2
node= 2
i= 3
visited= [0, 2, 3, 2, 1, 2]
q= deque([5])
node= 5
i= 4
node= 4
i= 1
i= 5
i= 3
node= 1
i= 3
i= 4
node= 3
i= 1
i= 4
i= 2
node= 2
i= 3
visited= [0, 3, 4, 3, 2, 1]
3

개인적으로 이 문제 bfs 공부하기 굉장히 좋은 문제라고 생각한다.

하여 좀 귀찮지만 모든 로그를 찍어보기 위하여 위와 같이 결과 값도 첨부한다

bfs의 가장 큰 특징은 가까운 정점부터 방문한다는 것이다.

위 문제에서 최초 1이 들어가게되면 

visited의 형태는 = [0,1,0,0,0,0] 

graph = [[],[3,4],[3],[1,4,2],[4]] 

이런식일 테다.

bfs 를 풀때마다 최초에 visited에 1을 넣는것이 좀 의아했었다. 근데 이렇게 로그로 찍어보니까 어차피 모든 visited에 1을 더해주니까 결과값에는 영향이 없다는것을 눈으로 확인 할 수 있었다.

다른사람의 풀이

개인적으로 dfs 공부하기에 정말 좋다고 생각했던 문제중에 하나인거같다.

https://www.acmicpc.net/problem/14888

A = int(input())
B = list(map(int,input().split()))
C = list(map(int,input().split()))

Maximum = -1e9 // 1e9=10^9을 의미한다.
Minimum = 1e9 


def solution(depth,count,add,sub,mul,div):
     global Maximum,Minimum
     if depth == A:
          Maximum = max(count,Maximum)
          Minimum = min(count,Minimum)

          return
     if add:
          solution(depth+1,count+B[depth],add-1,sub,mul,div)
     if sub:
          solution(depth+1,count-B[depth],add,sub-1,mul,div)
     if mul:
          solution(depth+1,count*B[depth],add,sub,mul-1,div)
     if div:
          solution(depth+1,int(count/B[depth]),add,sub,mul,div-1)


solution(1,B[0],C[0],C[1],C[2],C[3])
print(Maximum)
print(Minimum)

C에 연산자들을 담고 solution 한번 돌 때 마다 count에 다가 값을 갱신, 쓴 연산자들을 한번씩 - 해주는 단순한 코드이다. 다만 나눗셈 할때만 조금 주의하면 될거같다.