•알고리즘(Algorithm )/문제풀이

[백준14502&파이썬] 조합과 BFS탐색을 적절히 활용하는 구현문제에서는 시작점에 대한 고민을 해보자

# 문제 백준 14502 연구소 파이썬 풀이 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net # 코드 ''' - 브루트 포스를 이용해 모든경우의 수에 벽을 다 세워보자 - 64 * 63 * 62의 벽을 세울 수 있는 경우의 수가 생긴다. 25만 - 벽을 세우고 바이러스를 퍼트린 후 안전영역을 카운팅 해야한다. - BFS를 이용해 완전 탐색을 할때 시간 복잡도 - 백트래킹느낌으로 풀어봐야겠다. ''' import sys from collections import deque def print2D(arr) : for i in a..

[백준14938&파이썬] 플로이드와샬을 활용해 모든 정점에서 시작하여 모든정점까지 도착하는 경우를 구하자

# 문제 백준 14938 서강그라운드 파이썬 풀이 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net # 코드 ''' - 한 정점에서 모든정점까지의 최단거리를 구하자. ( X ) - 다익스트라 알고리즘 ?? - 아니다 문제를 잘못 봤다. - 플로이드 와샬로 모든정점에서 모든정점까지의 최단거리를 구해야 한다. ''' import sys def print2D(arr) : for i in arr : print(*i) # n : 지역의 개수 # m : 수색범위 # r : 길의 개수 n, m, r = map(int, sys.st..

[백준12851&파이썬] BFS를 이용해 최단시간 도착과 최단시간의 모든경우의 수를 구하자

# 문제 백준12851 숨바꼭질2 파이썬 풀이 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net # 코드 import sys from collections import deque from collections import defaultdict N, K = map(int, sys.stdin.readline().split()) dirs = [ -1, 1 ] visit = [False] * (100_001) visit[N] = True dq = deque() dq.append((N..

[백준13549&파이썬] BFS에서 큐에 넣을때 때때로 순서도 중요하다.

# 문제 백준 13549 숨바꼭질3 파이썬 풀이 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net # 코드 ''' - 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 구해라 - BFS로 최단시간 탐색을 수행하자. - 각 초마다의 위치가 나오기 때문에, 무조건 찾는다는 조건이 내재되어 있어 보이기 때문에 가능할듯 보인다. ''' import sys from collections import deque from collections import defaultdict # N = 수빈이..

[백준2638&파이썬] BFS에 구현과 시뮬레이션이 섞인 문제

# 문제 백준 2638 치즈 파이썬 풀이 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net # 코드 import sys from collections import deque def show2D(arr): for i in range(len(arr)): print(*board[i]) N, M = map(int, sys.stdin.readline().split()) board = list() dirs = [ (-1, 0), (0, 1), (1, 0), (0, -1) ] candidaties = list(..

[백준1932&파이썬] DP를 이용할때 확정지을 노드를 선택하는 기준과 근거가 필요하다.

# 문제 백준 1932 정수 삼각형 파이썬 풀이 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net # 코드 import sys n = int(sys.stdin.readline().strip()) arr = list() for _ in range(n) : line = list(map(int,sys.stdin.readline().split())) arr.append(line) for row in range(1,n): for col in range(len(arr[row])) : if col == 0 : # 시작점이면 arr[row][col] += arr[row-1][col] continu..