본문 바로가기

알고리즘19

[BOJ] 1012 유기농 배추 - python 1012번: 유기농 배추 (acmicpc.net) 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net '11724 연결 요소의 개수 문제'와 '13565 침투' 문제를 합친 문제 같았다. 실제로도 위 두 문제를 합치니 해결이 가능했다. dfs를 이용하여 더 이상 재귀를 불러올 수 없을 경우 count를 증가시켜주는 방식으로 풀었다. 나는 행렬 형태에 입력 값을 넣었는데, 백준에서 그려놓은 그림과 같이 입력을 받으려면 입력받는 x,y 값과 행렬을 호출하는 x,y값이 반대라는 것을 주의해야한다. import sys sys.set.. 2022. 3. 27.
[개념] Dijkstra(다익스트라) - python 다익스트라 알고리즘 - 유향 그래프에서 간선들의 가중치가 모두 0 이상인 경우의 최단 경로 알고리즘 왜 가중치가 0 이상이어야 할까? - 다익스트라 알고리즘에서 최단 거리를 저장한 노드는 집합에 포함시켜 놓는데, 집합에 포함된 노드의 최단 거리 값은 다시 계산하지 않는다. 그러나 가중치가 음수일 경우, 최단 거리 값이 바뀌어 노드에 저장해 놓은 최단 거리 값을 바꿔야하는 경우가 발생할 수도 있다. 하지만 집합에 포함된 노드는 값을 수정할 수 없기 때문에 다익스트라 알고리즘은 간선의 모든 가중치가 0 이상일 때 성립한다. 다익스트라 알고리즘에서의 가정 두 정점 간 경로가 존재하지 않으면 경로의 가중치는 무한대로 정의한다. 두 정점 간 간선이 존재하지 않으면 가중치가 무한대인 간선이 존재한다고 간주한다. 다.. 2022. 3. 24.
[BOJ] 11724 연결 요소의 개수 - python 백준 11724번 연결 요소의 개수 문제이다. import sys sys.setrecursionlimit(10000) N, M = map(int,sys.stdin.readline().split()) visited = [0]*(N+1) graph = [[0]*(N+1) for _ in range(N+1)] def dfs(n): visited[n] = 1 for i in range(1,N+1): if visited[i] == 0 and graph[n][i] == 1: dfs(i) for _ in range(M): a, b = map(int, sys.stdin.readline().split()) graph[a][b] = 1 graph[b][a] = 1 count = 0 for _ in range(1,N+1):.. 2022. 3. 23.
[BOJ] 13565 침투 - python 백준 13565번 침투 문제이다. import sys sys.setrecursionlimit(1000000) M, N = map(int,sys.stdin.readline().split()) visited = [[0]*(N) for _ in range(M)] graph = [] for _ in range(M): a = list(map(int, sys.stdin.readline().rstrip())) graph.append(a) def dfs(x,y): if x = M or y = N: return if graph[x][y] == 0 and visited[x][y] == 0: # graph[x][y]가 갈 수 있는 길이고, 방문 된 적 없으면 visited[x][y] = 1 dfs(x,y-1)# 좌 dfs(.. 2022. 3. 23.

티스토리툴바