DFS
-
알고리즘: 백준 1238번 파티 (feat. python)알고리즘/백준(BaekJoon) 2021. 1. 11. 20:07
1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net import sys import heapq read = sys.stdin.readline N, M, X = map(int, read().split()) graph = {i: []for i in range(1, N+1)} # 각 마을에서 X로 가는 방향 그래프 graph2 = {i: []for i in range(1, N+1)} # X에서 각 마을로 가는 그래프 for _ in range(M): s, e, l = map(int, re..
-
알고리즘: 백준 11724번 연결 요소의 개수 (feat.python)알고리즘/백준(BaekJoon) 2021. 1. 8. 10:57
11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net import sys read = sys.stdin.readline n, m = map(int, read().split()) graph = {} for i in range(n): graph[i+1] = [] for _ in range(m): u, v = map(int, read().split()) graph[u].append(v) graph[v].append(u) global count count = 0..
-
알고리즘: 백준 1012번 유기농 배추 (feat. python)알고리즘/백준(BaekJoon) 2021. 1. 7. 18:47
1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net import sys read = sys.stdin.readline case = int(read()) def sol(): global count count = 0 m, n, bae = list(map(int, read().split())) box = [[0 for _ in range(m)] for _ in range(n)] for _ in range(bae): x, y = list(map(int, read().split())) box[y][x] = 1 for i in rang..
-
알고리즘: 백준 2606번 바이러스 (feat.python)알고리즘/백준(BaekJoon) 2021. 1. 4. 23:28
2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net import sys read = sys.stdin.readline def bfs(start, dic): queue = [start] while(queue): pop = queue.pop(0) for i in dic[pop]: if i not in visited: visited.append(i) queue.append(i) def dfs(start, dic): for i in dic[start]: if i not in visited: visited.append(i) d..
-
알고리즘: 되추적(Backtracking) 공부하기! (N-Queens problem을 풀어보자)알고리즘 2020. 11. 9. 20:11
되추적은 임의의 집합에서 주어진 기준대로 원소의 순서를 선택하는 문제를 푸는데 사용한다. 전형적인 사례로 체스의 n-Queens Problem이 있다. 이 문제의 목표는 n x n 크기의 서양 장기판에 서로 잡아먹히지 않도록 n개의 여왕말을 위치시키는 것이다. 즉, 어떤 여왕말끼리도 같은 행이나 열, 대각선상에 위치할 수 없다. 이 문제에서 순서는 여왕말을 둘 n개의 각각 다른 위치이고, 집합은 서양 장기판에서 말을 둘 수 있는 n제곱개의 위치들이 되고, 기준은 어떤 여왕말도 서로 잡아 먹히지 말아야 한다는 것이다. 되추적은 트리의 변형된 깊이우선탐색(DFS)이다. DFS에 대해 간단히 설명하면 부모의 노드에서 내려갈 수 있는 자식노드까지 내려가고 그 이후의 자식 노드가 없다면 다시 부모노드로 돌아가면서..
-
알고리즘: 백준 11048번 이동하기 (feat. python)알고리즘/백준(BaekJoon) 2020. 8. 27. 22:42
백준 11048번 링크입니다. 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 �� www.acmicpc.net DFS 인줄 알았지만 시간초과가 나길래 다시 보니 다이나믹프로그래밍이였던 문제 dp를 이차원 리스트로 만들어서 dp[N][M] = (N, M)까지 오기까지의 합이라고 한다면 dp[N][M] = max(dp[N - 1][M], dp[N][M - 1], dp[N - 1][M - 1]) + maze[N][M] 라고 할 수 있다. import sys input = sys.stdin.readline N, M = map(in..
-
알고리즘: 백준 2293번 동전 1 (feat. python)알고리즘/백준(BaekJoon) 2020. 8. 25. 20:51
백준 2293번 링크입니다. 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 결론부터 말하면 dp를 이용해 풀어야 풀린다. 시간제한이 0.5초로 dp를 제외한 다른 방법을 쓰기가 까다롭다. 처음에는 dfs를 이용해 풀었지만 시간초과가 나길래 결국은 다른 분의 답을 참고하였다. import sys class Node: # 방문처리를 위해 노드 클래스를 만들었다. def __init__(self, data): self.data = data def dfs(start, tar..
-
알고리즘: 백준 14888번 연산자 끼워넣기(feat. python)알고리즘/백준(BaekJoon) 2020. 8. 24. 22:08
백준 14888번 링크입니다. 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 이렇게 열심히 풀긴 했지만 결국 틀렸다... 하지만 이 문제 하나로 여러가지 경험을 한 것 같아서 만족한다. permutation이라는 편리한 모듈을 알게 되었고 stack과 dfs에 대해서 좀 더 깊게 알 수 있었다. permutation을 통해서 가능한 연산자순서의 경우의 수를 구했고 stack을 통해 필요한 값을 넣고 뺌으로써 원하는 값을 구하는 방법을 체득하였다. i..