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 >> ..

*다익스트라의 정석 문제 #include #include #include #include #include #define INF 987654321 #define max_v 20001 #define max_e 300001 using namespace std; int V, E; // graph[i]={j,w} : i 에서 j노드로 가는 가중치 w vector graph[max_v]; int dist[max_v]; // distance[j] : 출발노드에서 j노드까지의 거리, 초기엔 모두 INF void dijst(int start) { for (int i = 1; i w) { dist[toNode] = w; pq.push({ w, toNode }); } } } return; } int main() { cin...

1. 풀이 (1) 각 성별을 정렬한다. 남자성격과 여자성격을 정렬했을 때 총 차이의 합이 최소가 되기위해선 항상 아래의 조건이 만족한다. (n번째남자와 매칭된 여자의 성격수치) j이면 j여자에게 잘맞는 여러명의 남자중 하나를 고른다 dp[i][j]=min(dp[i][j],d[i-1][j]) - ij: d[i][j]=min(d[i][j],d[i-1][j]) ..

1.풀이 (1) 25개의 위치에 n개의 조각을 둘 수 있는 모든 경우의 수를 구한다 (조합을 이용, n은 최대 5이므로 총 횟수는 최대 25C5=53130) (2) (1)에서 구한 모든 경우에 대해 해당경우가 연결되어 있는 상태인지 구한다 (BFS를 이용한다) (3) 연결되어 있다면 원래상태에서 해당경우를 만들 수 있는 최소상태를 구한다. (각 조각에 고유번호를 매기고, 순열을 이용하여 모든 경우를 확인한다.) 2. 소스코드 from itertools import combinations,permutations from collections import deque dR=[0,0,-1,1] dC=[1,-1,0,0] INF=9876543210 def calDist(A,B): return abs(A[0]-B[0..

트리순회 트리를 순회할 때 어떤 노드를 먼저 탐색하느냐에 따라 전위,중위,후위로 나눌 수 있다. 각각의 순회를 알아 본다. 전위순회 부모 -> 왼쪽자식 -> 오른쪽자식 더이상 부모노드가 없을때 그 다음 노드(왼쪽자식)을 탐색한다 중위순회 왼쪽자식 -> 부모 -> 오른쪽자식 더이상 왼쪽자식이 없을때 그다음 노드(부모)를 탐색한다 후위순회 왼쪽자식 -> 오른쪽자식 -> 부모 그다음 왼쪽자식이 없을때 그다음 노드(오른쪽자식)을 탐색한다 *출처 : https://hongku.tistory.com/160 예시코드 (백준 1991 트리순회) def preorder(N): global graph if N in graph: print(N, end="") preorder(graph[N][0]) preorder(graph..

1. 풀이 (1) 입력이 하나의 그래프임이 보장될때 트리일 조건은 (노드개수-1)==(간선개수)가 된다. (2) 간선개수가 0인것은 빈트리이므로 이것역시 트리이다. 2. 소스코드 #include #include #include #include using namespace std; int main() { int num1, num2; string ans; int t = 1; while (1) { cin >> num1 >> num2; if (num1 < 0) { break; } // test case else { vector graph; set s; // 입력 while (1) { if (num1 == 0 and num2 == 0) { break; } else { graph.push_back(make_pair..

1. 함수의 구성 유니온 파인드는 find와 union 두가지 함수로 구성이 된다. (1) find는 그래프에서 루트노드를 찾아주는 함수이다. int find(int x) { if (parent[x] == x) { return x; } else { return parent[x] = find(parent[x]); } } (2) union은 서로 연결되어 있지 않은 그래프를 연결시키는 함수이다. void Union(int x, int y){ x = find(x); y = find(y); if(x!=y){ parent[y] = x; } } 2. 함수의 사용 유니온 파인드는 아래의 두가지 경우에 사용할 수 있다. (1) 그래프가 연결되어 있는지 확인할 때 (ex [boj]1717_집합의 표현) 어떤 두 노드의 ..