728x90 코딩테스트25 BFS 백준 - 13913 [Python] Problem) https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net Solution) from[i] = 어디에서 왔는지 의미: from[i] -> i N에서 K를 가는 문제이기 때문에 K부터 from을 통해서 N까지 가야한다. 즉, 역순으로 저장되기 때문에, 다시 역순으로 구하는 것이 필요하다. Answer) from collections import deque import sys MAX = 200000 sys.s.. 2021. 8. 27. BFS 백준 - 1697 [Python] 목적은 임의의 정점에서 시작해서, 모든 정점을 한 번씩 방문하는 것이다. BFS는 모든 가중치가 1일때, 최단 거리를 구하는 알고리즘이다. - 최소비용 문제이어야 한다. 가중치가 1이 아닐때에는 다익스트라 알고리즘을 사용해야 한다. 정점과 간서의 개수가 적어야 한다. Problem) https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net Solution) 입력의 제한은 10만, 갈 수 있는 것은 20만이 최대가 된다. che.. 2021. 8. 27. BFS 백준 - 2667 [Python] Problem) https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net Solution) 이 문제같은 경우에는, 인접리스트로 굳이 풀 필요가 없다. 왜냐하면 i행 j열을 알고있을 경우, 인접한 부분은 상,하,좌,우 밖에 없기 때문이다. 따라서 이 문제의 경우, 정점의 경우 정수 2개의 조합으로 문제를 해결하면 된다. d[i][j] = (i,j)를 방문안했으면 0 했으면 단지번호를 넣는다. Answer) from collections import dequ.. 2021. 8. 20. DFS 목적 : 한 정점에서 시작해서 연결된 모든 정점을 한 번씩 방문하는 것 DFS의 경우 재귀호출을 통해서 구현하도록 한다. 인접행렬 버전 이때, DFS의 x호출은 x를 방문했다는 것이다. 따라서 방문 표시를 해 주고, 이제 그 다음 정점을 찾아야 한다. 그 다음 정점은 x에서 i사이의 간선이 있어야 한다. i를 방문한적이 없음 위 2가지 조건을 만족해야지 이동할 수 있다. 이때 시간 복잡도는 O(V^2)이다. def dfs(int x): check[x] = True for i in range(1,n+1): if a[x][i] == 1 and check[i] == False: dfs(i) 인접리스트를 사용할 경우, x에서 i를 찾는 방법만 변경해주면 된다. 인접리스트에서 a[x]에 들어있는 것은 x와 연결된.. 2021. 8. 20. 이전 1 2 3 4 ··· 7 다음 728x90