1.풀이 (1) 2개의 연결된 그래프를 만들기 위해선 크루스칼 알고리즘을 적용한 뒤 가장 큰 간선을 하나 빼면된다. 이때 가장 큰 간선은 N-1번째에 들어오는 간선이므로, 2개의 mst를 만들기 위해선 간선을 N-2번째까지 추가해 주면 된다. (2) 최소간선부터 하나씩 넣어볼 때, pq를 쓰는방법과 sort를 하고 앞에서부터 뽑는 방법이 있다. 결과는 아래와 같다. 소스코드1 : edge.pop(0)을 해줌 ->시간초과 소스코드2 : edge[i]로 참조해줌 -> 통과 (5696ms) 소스코드3 : heapq.heappop() -> 통과 (6992ms) *pq는 매번 pop하고 정렬해주어야 하기 때문에 한번 정렬 후 앞에서 부터 참조하면 되는 소트보다 느림 단, 소트후 앞에서..

1. 풀이 플로이드와샬의 정석 k 포문이 돌아갈때 L[i][j]의 의미 : k정점까지 사용이 가능할 때 i에서 j까지의 최단거리 * 초기화시 주의할점 L[i][j]가 (1) if i==j 이면 => 0 (2) if i!=j 이면 => inf 으로 초기화할것! 2. 소스코드 N,M=map(int,input().split()) maxNum=9876543210 L=[[maxNum for j in range(N+1)] for i in range(N+1)] for i in range(1,M+1): a,b=map(int,input().split()) L[a][b]=1 L[b][a]=1 for i in range(1,N+1): L[i][i]=0 for k in range(1,N+1): for i in range(1,..

1. 풀이 (1) 벨만포드를 적용할 때 경로를 저장한다. * 처음엔 특정 노드에서 어디로 가는지를 저장했다. 하지만 이렇게 하면 우리가 원하는 목적지로 가는 경로가 나오는것이 아니라 입력 순서에 영향을 받아 해당 노드에서 어떠한 다른 노드로의 최단경로의 일부가 저장될 수 있다. ex) 1-2, 1,3이 있고 3이 목적지일때 1노드의 방향이 2노드를 향할 수 있다. 따라서 특정 노드가 어느 노드에서 오는지를 저장해야한다. (즉 이전 노드가 무엇인지를) ​ (2) 벨만 포드를 적용한 후 싸이클을 확인해야한다. 이때 경우의 수는 다음과 같다 1. (출발지에 붙은)사이클이 있다 (​isUpdate==True) (1) 도착지와 붙어있다. (q를 통해서 확인, connectCycle==True) => -1 (2) ..

1. 풀이 가중치 있는 그래프이므로 일반적인 다익스트라 알고리즘을 사용하면 되는데, 특정 경로를 지났는지를 확인해주어야 한다. 다익스트라는 아래와 같이 구성된다. while(dij): nowDist,nowNode,isCon=heapq.heappop(dij) if nodeDist[nowNode]

1. 풀이 이분그래프를 확인하는 방법은 다음과 같다. (1) 2개의 색깔을 가지고 dfs를 통해 인접한 노드에 다른 색깔을 칠하며 전체를 다 칠하기. (2) 2중 포문을 통해 인접한 노드에 다른색이 칠해져 있는지 확인. -> 다른색이 칠해져 있으면 이분그래프 될 수 없음. (3) 이분그래프 2. 소스코드 import sys sys.setrecursionlimit(10 ** 7) k = int(input()) turn = [1, 0] def cheak(): for v in range(1, V + 1): nowColor = colorV[v] for conNode in graph[v]: if colorV[conNode] == nowColor: print("NO") return print("YES") def d..

1. 최단거리 2. 최소스패닝 트리(MST)

1.풀이 [백준]1035 조각움직이기 (https://sosoeasy.tistory.com/39) 와 비슷한 문제이다. (1) 모든 경우의 수를 조합으로 구한다 (2) (1)에서 구한 경우가 임도연파(Y)가 4명이상인지 확인한다. (3) 4명이상이면 bfs를 통해서 연결되어있는지 확인한다. - 소스코드1 : dfs를 이용하여 연결여부 확인 - 소스코드2 : bfs를 이용하여 연결여부 확인 -> 내생각엔 이게 더 쉽다. * 이런류의 문제를 백트래킹으로 생각하면 조건 처리가 힘들어지는 경우가 많다. 완전탐색으로 보이는 문제는 깔끔하게 순열, 조합으로 풀 수 없을까 고민하는 자세가 필요하다. 2. 소스코드 (1) 소스코드1 (dfs를 이용) from itertools import combinations dR=..

구글링 해보니 4차원 dp를 이용해서 푼사람들이 많았다. 나는 안똑똑해서 dfs를 이용하여 풀었다. 1. 풀이 [백준]4991 로봇청소기(https://sosoeasy.tistory.com/24) 문제와 유사하다. 아래의 순서를 따른다. (1) 현재위치에서 남아있는 모든 C까지의 거리를 bfs를 통해서 구한다. (2) (1)에서 구한 모든 경우에 대해서 해당 점을 시작위치로 하여 dfs를 한다. 2. 소스코드 INF=9876543210 from collections import deque dR=(-1,0,1,0) dC=(0,-1,0,1) N,M=map(int,input().split()) L=[] for i in range(N): L.append(list(input())) def bfs(case,q,vi..

1. 풀이 그래프에서 음의 사이클이 단 하나라도 있으면 벨만포드의 V번째 반복에서 최솟값(nodeDist)의 갱신이 일어난다. 따라서 웜홀의 유무는 벨만포드 알고리즘을 이용하여 풀 수 있다 ​ 2. 주의사항 1. 도로는 양방향임 2. 도로와 웜홀은 모두 연결되어있다고 가정.(여러개의 컴포넌트 tc가 현재까진 없음) 현재 알고리즘은 임의의 점(1번노드) 하나를 잡아서 연결된 모든 노드들까지의 최단거리를 구한다. 따라서 임의의 시작점과 연결되어있는 그 음의 사이클만 확인할 수 있다. 아래가 반례이다. TRUE가 나와야 하지만 음의사이클이 시작점과 연결되어있지않아 음의사이클을 검출하지못하고 FALSE가나옴 1 5 1 3 1 2 3 3 4 1 4 5 1 5 3 1 따라서 위의 경우(연결되어있진 않지만 음의 사이..

1.풀이 (1) 목적지에서 벌수있는 돈을 음(-)으로, 이동비용을 (+)로 두고 간선의 가중치를 부여한다 (2) 벨만포드로 최단 거리를 구하기 위해 N-1번 edge relaxation 수행한다. (3) N번째에서 아래의 사항을 확인 - 음의 사이클이 있는지(nodeCost[n1]+cost"gg" - (시작부분과 연결된)음의사이클이 존재하고, 해당 음의 사이클에서 목적지로 이동이가능할때(bfs로확인)->"gee" - 그렇지않은경우(목적지까지 도달할수있고, 음의사이클이 존재하지만 목적지로 도달할수 없는경우 or 음의사이클 존재안하는경우) -> 값출력 (-1곱할것) ​ *많이틀림 처음에 출발지에서 임의의 음의 싸이클까지 연결이 되있는지를 확인해주는 N번째반복의 조건문(nodeCost[n1]!=maxNum)를..

파티에 진실을 아는사람이 있으면 진실만을 말해야 한다. 새롭게 진실을 알게 된 사람을 고려해야한다(그사람이 참석하는 다른 파티에서도 진실을 말해야한다) ​ 1. 풀이 (1) 그래프 연결 1) 파티를 하나의 노드로 본다. 2) 파티를 두개씩 짝지어서 비교하면서, 한사람 이상을 공유하면 연결한다. (파티1과 파티2를 비교하여 둘다 참여하는사람이 있으면 연결한다.) 3) 연결이 완료되면 탐색을 시작한다. (2) 탐색 1) 연결된 노드(파티)들을 탐색한다 2) 연결된 파티들 중 하나의 파티에서라도 진실을 아는사람이 있다면, 연결된 모든 파티에는 진실을 말해야한다 3) 한명도 진실을 아는사람이 없다면 연결된 모든 파티에는 과장을 해도된다. ​ 2. 소스코드 from collections import deque N..

1. 풀이 (1) 설치횟수의 최솟값을 구한다. 설치할때만 이동거리를 +1해주고, 그렇지 않은 노드간의 연결은 +0 (2) 즉 간선간의 가중치가 다르므로(1 or 0) bfs가 아닌 다익스트라를 이용한다. (bfs로 탐색하면, 처음으로 다른문(#)을 찾은 경우가 거울의 최소설치가 아닌, 거울설치에 제약이 없을 때 최소이동 경로가 된다. 따라서 모든경우를 다 탐색한 후 그 중 최소설치횟수를 찾아야함.) (3) 이 문제는 특히 이동방향 상의 제약(빛은 직진만함)이 있기 때문에 한 노드(r,c)에 총 4번까지 방문이 가능하다. 따라서 한 노드 nodeDist[r][c]에 4방향의 저장소를 만든다 즉 nodeDist[r][c][k] : r,c에 k방향일때의 최소 설치횟수 ​ 2. 소스코드 import heapq ..

1. 풀이 최소스패닝트리(MST)문제. 크루스칼 알고리즘을 사용한다. 사이클을 확인하기 위해 유니온파인드를 이용해아햐며, 이때 dfs(or bfs)를 사용하면 시간초과가 난다. ​ 2. 소스코드 (1) dfs,시간초과 import heapq from collections import deque def isCycle(L): visited=[-1 for i in range(V+1)] stack=deque([L[0][0]]) while(stack): temp=stack.pop() # 스택에 있으면 싸이클 if temp in stack: return True visited[temp]=1 for n1,n2 in L: if n1==temp and visited[n2]==-1: stack.append(n2) elif..

어떤노드에 처음으로 방문한 순간이 최단거리임이 보장된다(bfs와 비슷). 따라서 주어진 끝노드에 도달하면 해당 비용을 출력한 후 종료한다. import heapq N=int(input()) M=int(input()) graph={} for i in range(N): graph[i+1]=[] for i in range(M): a,b,c=map(int,input().split()) graph[a].append([b,c]) start,end=map(int,input().split()) maxNum=9876543210 nodeDist=[maxNum for i in range(N+1)] dij=[[0,start]] heapq.heapify(dij) while(dij): temp=heapq.heappop(dij) ..

1. 문제요약 (1) dfs,dp문제의 정석 (2) 사이클x (3) 가능한 경로의 개수(최단경로 아니다!) 2. 풀이 (1). 일단 가능한 경로를 모두 찾아야 하기 때문에 dfs로 모두 찾는다. (2). 초기값은 -1로 지정해준 후, 이때 한번 지나간 곳은 다시갈 필요가 없으므로 0으로 바꿔준다. (3). 이후 리턴을 받을때 +1씩 해준다 * 설명이 잘되어있는 블로그(단, 초기값이 0으로 되어있어서 시간초과가 난다) https://wootool.tistory.com/83 [백준][1520번][DP] 내리막길 내리막길 https://www.acmicpc.net/problem/1520 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ..

1. 풀이 1) 다음의 두가지 거리가 필요하다. (파티장 x에서 a까지의 최단거리) + (a에서 파티장x까지 최단거리) 2) (파티장 x에서 a까지의 최단거리) : X를 시작점으로 다익스트라를 이용해서 구한다 3) (a에서 파티장x까지 최단거리) : edge를 모두 반대방향으로 바꾼 후(cost는 그대로) 다익스트라. 위가 성립하는 이유는 (graph에서 a->b 까지의 최단거리) == (edge의 방향을 바꾼 graph에서 b->a까지의 최단거리) 이기 때문에 자명하다. 2. 소스코드 import heapq #input N,M,X=map(int,input().split()) graph={} graphR={} for i in range(1,N+1): graph[i]=[] graphR[i]=[] for i..

모든 노드들을 최소한의 비용으로 연결한 트리를 최소신장트리(mst)라고 한다. 최소신장 트리를 만드는 방법은 여러가지가 있다. ​ 1. 크루스칼 알고리즘 1) 모든 간선들을 오름차순으로 정렬한다. 2) 가중치가 작은 간선부터 하나씩 연결한다. 3) 간선을 연결했을 때 사이클이 생기면 해당 간선은 제거하고 다음 간선을 붙인다. 4) 간선의 개수가 (node개수 - 1)이 될때까지 간선을 이어붙인다. ​ https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221230994142&proxyReferer=https%3A%2F%2Fwww.google.com%2F 18. 크루스칼 알고리즘(Kruskal Algorithm) 이번 시간에 다루어 볼 내용은 바로 크루스..

1. 위상정렬? 2. 방법 어떠한 노드의 관점에서 그 노드로 들어오는 간선의 수를 진입차수라고 한다. 그리고 이러한 진입 차수가 0인 노드가 항상 시작 노드가 된다. 기본적인 알고리즘은 이러한 시작노드들을 큐에 넣고, 시작노드들과 연결되어 있는 다음 순서의 노드들 사이에 간선들을 없애며, 그 과정에서 새롭게 진입차수가 0이된 노드들을 다시 큐에 넣는 방식으로 진행된다. 3. 소스코드 #include #include #include #include using namespace std; // 부무노드 개수 저장 int parent[32001]; // togo[i]에는 i가 향하는 정점들을 저장 vector togo[32001]; queue q; int main() { int N, M; cin >> N >> ..