7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net """ 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향 에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 현수는 창고에 보관된 토마토들이 며칠이 지나 면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다. 첫 줄에는 상자의 크기를..

분석 [2667] 단지번호붙이기(BFS) 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 karla.tistory.com [17472] 다리 만들기2 (BFS, MST) 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바 karla.tistory.com 풀이 """ 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있음. 0은 바다 섬나라 아일랜드에 몇 개의 섬이 있는지 첫 번째 줄에 자연수 N(3

분석 풀이 """ 현수의 농장은 N*N 격자판, 각 격자안에는 한 그루의 사과나무가 심어저 있다, N의 크기는 항상 홀수 사과를 수확할 때 다이아몬드 모양의 격자판만 수확하고 나머지 격자안의 사과는 새들을 위해서 남겨놓는다. 입력 첫 줄에 자연수 N(홀수)이 주어진다.(3

13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 분석 [1260번] DFS, BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. karla.tistory.com 풀이 import sys input=sys.stdin.readline sys.setrecursionlimit(10000) n,m=map(int,input().split()) # 사람수, 친구관계수 list = [[] for _ in range(n+1)] for _ in..

정리 다익스트라 크루스칼 용도 일대다 정점 간의 최소 거리 파악 최소 신장 트리(MST) 파악 중심 정점(Node) 간선(Edge) 모든 정점 방문 X O 구현 방법 우선 순위 큐 + dist[점화식] 우선 순위 큐 + Union-Find 시작점 출발점이 정해져 있는 경우 간선 가중치가 작은 것부터 큐에 넣는 시점 dist가 갱신 될 때 그 점에서 출발하는 간선을 큐에 넣음 모든 정점을 우선순위 큐에 넣고 시작 끝 점과 점 사이의 최단 거리를 찾고 나면 더이상 탐색하지 않음 최소신장 트리가 만들어 질 때까지 탐색 최소 임의의 두 점 간의 최소 거리를 구할 때 사용 최소 비용으로 모든 점을 다 이을 때 사용 임의의 두 점 간의거리 최소 보장 X 최단거리 알고리즘 그래프 최단거리 알고리즘 정리 및 비교 (다..

24042번: 횡단보도 당신은 집으로 가는 도중 복잡한 교차로를 만났다! 이 교차로에는 사람이 지나갈 수 있는 $N$ 개의 지역이 있고 그 지역 사이를 잇는 몇 개의 횡단보도가 있다. 모든 지역은 횡단보도를 통해 직, www.acmicpc.net 분석 시간 역행 불가, 이미 지난 가중치로 지나갈 수 없음 ➔ 주기 이전 소요 시간 ≤ 지금 이용하는 시간 값이 될 때까지 M을 여러 번 더하여(곱하여) 사용 풀이 import heapq import sys input = sys.stdin.readline n, m = map(int, input().split()) graph = [[] for _ in range(n+1)] for i in range(m): a, b = map(int, input().split())..