Coding Test/Graph

[2468] 안전영역(BFS)

2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 6 8 2 6 2 3 2 3 4 6 6 7 3 3 2 7 2 5 3 6 8 9 5 2 7 """ 어떤 지역의 높이 정보를 파악, 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역 최대 몇 개인지 조사 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠김 안전영역 : 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역 높이가 4 이하인 모든 지점이 물에 잠김 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠..

섬나라 아일랜드(BFS)

분석 [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

단지번호 붙이기(DFS)

더보기 [2667] 단지번호붙이기(BFS) 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 karla.tistory.com 풀이 # 네 방향 탐색을 위한 상수 → ↓ ← ↑ dr=[0,1,0,-1] dc=[1,0,-1,0] n=int(input()) graph=[list(map(int, input())) for _ in range(n)] # print(graph) res= [] def dfs(x,y): global cnt cnt+=1 graph[x][y]=0 # 방문처리 for i in range(4): # 네방향 nextX=x+dr[i] nextY=y+d..

[2667] 단지번호붙이기(BFS)

2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 분석 [17472] 다리 만들기2 (BFS, MST) 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바 karla.tistory.com 풀이 """ 1은 집이 있는 곳을, 0은 집이 없는 곳 연결된 집들의 모임인 단지를 정의하고, 단지에 번호 붙이려한다 단지수를 출력, 각 단지 에 속하는 집의 수를 오름..

등산경로(DFS)

""" 마을 뒷산의 형태를 나타낸 지도 N*N, 각 구역에 높이 나타남 다른 구역으로 등산을 할 때는 그 구역의 위, 아래, 왼쪽, 오른쪽 중 더 높은 구역으로만 이동 가능 등산로의 출발지는 전체 영역에서 가장 낮은 곳이고, 목적지는 가장 높은 곳 출발지와 목적지는 유일 출발지에서 도착지로 갈 수 있는 등산경로 가지수 출력 첫 번째 줄에 N(5

미로탐색(DFS)

""" 7*7 격자판 미로를 탈출하는 경로의 가지수를 출력 출발점은 격자의 (1, 1) 좌표이고, 탈 출 도착점은 (7, 7)좌표 격자판의 1은 벽이고, 0은 도로 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 0 0 1 0 0 0 0 0 0 위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지 """ import sys input = sys.stdin.readline # 네 방향 탐색을 위한 상수 → ↓ ← ↑ dr=[0,1,0,-1] dc=[1,0,-1,0] graph= [list(map(int, input().split())) for _ in range(7)] cnt=0 def dfs(x,..

미로의 최단거리 통로(BFS 활용)

분석 [2178] 미로 탐색(BFS) """ 두 정수 N, M(2 ≤ N, M ≤ 100) M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. """ import sys from collections import deque input = sys.stdin.readline n, m = map(int, input().split()) # 네 방향 karla.tistory.com 풀이 """ 7*7 격자판 미로를 탈출하는 최단경로의 경로수를 출력 경로수는 출발점에서 도착점까지 가는데 이동한 횟수 출발점은 격자의 (1, 1) 좌표이고, 탈 출 도착점은 (7, 7)좌표 격자판의 1은 벽이고, 0은 도로 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 0 1 1 0 1 0..

인접행렬(가중치 방향그래프)

그래프의 표현 및 비교 (간선 리스트, 인접 행렬, 인접 리스트) 간선 리스트 인접 행렬 인접 리스트 중심 간선 노드 노드 시간복잡도 - 느림 빠름 구조 [] d[시작노드][종료노드] d[시작노드] 입력 (시작노드 ,도착노드, 가중치) 가중치 (도착노드, 가중치) 알고리 karla.tistory.com """ 첫째 줄에는 정점수 n(2~20), 간선수 m m줄 연결정보와 거리비용 6 9 1 2 7 1 3 4 2 1 2 2 3 5 2 5 5 3 4 5 4 2 2 4 5 5 6 4 5 """ import sys input = sys.stdin.readline n, m = map(int, input().split()) d = [[0 for j in range(n)] for i in range(n)] for i..

[1414] 불우이웃돕기 (MST, 문자열)

1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 풀이 """ N개의 컴퓨터를 모두 서로 연결, 각각의 컴퓨터는 랜선으로 연결 기부할 수 있는 랜선의 길이의 최댓값 컴퓨터의 개수 N(1~50) 랜선의 길이 a~z: 1~26, A~Z: 27~52, (i,j)=0: 랜선이 없음 """ import sys input = sys.stdin.readline from queue import PriorityQueue n=int(input()) #컴퓨터개수 total=0 # 총 랜선 길이 pq = PriorityQueu..

최단거리(다익스트라) vs 최소 신장 트리(크루스칼)

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