1. 풀이 처음엔 dfs로 완전탐색했고 시간초과가 발생했다. (소스코드1) 규칙을 찾아서 풀어야 한다. 처음에 같은모양을 갖고 있지 않는 행은 열 단위로 스위치를 누를 때 절대 같아질 수 없다. 즉 (1) 동시에 켜져있는 행이 될 수 있는 행들 시작할 때 같은 모양을 갖는 행들 (union find로 찾았다) (2) 해당 집합이(같은 모양을 갖는 행들) k번째에 켜져있는상태가 될 수 있는가? 시작할때 0의 개수와 k를 2로 나눈 나머지가 같다 ​ 2. 소스코드1 (시간초과,dfs 완전탐색) N,M=map(int,input().split()) L=[] for i in range(N): L.append(list(input())) k=int(input()) def push(j): for i in range(N..

1. 풀이 더보기 시작점, 열쇠가 있는 모든 지점에서 로봇이 복제되고, 모든 열쇠를 얻어야 하며, 이때 모든 로봇의 이동거리를 구한다. 위의 문제가 MST문제임을 알면 구현은 매우쉽게 일반적인 MST를 푸는것과 같이 하면 된다. 하지만 위의 문제 MST문제인지를 알기가 어렵다. 따라서 조건을 어느정도 외워두고 비슷한 상황에서 MST를 떠올릴 줄 아는것이 중요해 보인다! 2. 소스코드 from collections import deque import sys dR=[0,0,-1,1] dC=[1,-1,0,0] N,M=map(int,input().split()) L=[] for i in range(N): L.append(list(input())) def dist(sR,sC,fR,fC): q=deque([[sR,..

1. 풀이 일반적인 mst문제이고, N개의 노드를 모두 연결하는 edge를 만들어서(nC2개) 크루스칼을 적용하면 정답은 맞지만 시간초과가 발생한다. (소스코드1)​ 시간초과를 줄일 수 있는 방법은 아래의 조건을 이용해서 사용하는 edge의 개수를 줄이는것. (소스코드2) 더보기 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 그리고 위조건을 이용하는 방법은 아래와 같다. (1) 1차원 좌표에서 N개의 점이 있고, 이때 N개의 점으로 mst를 만드는 방법은 왼쪽부터 i번째 점을 i+1번째 점과 연결해나가는 방법이다. (n-1개) (2) 3차원에서도 똑..

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

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

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_집합의 표현) 어떤 두 노드의 ..

dfs(stack)를 이용하여 그래프에서 사이클이 있는지 확인할 수 있다. 이때 그래프가 유향일때와 무향일때 방법이 각각 다르다. ​ 1. 무향그래프 (1) stack #싸이클인지 확인 def isCycle(L): visitedN=[] myL=list(L) stack=deque([myL[0][0]]) while stack: nowN=stack.pop() #싸이클인지 확인 if nowN in stack: #(if nowN in visitedN도 된다!) return True for i in myL: if nowN in i: if nowN==i[0]: other=i[1] else: other=i[0] if other not in visitedN: stack.append(other) visitedN.appen..