Coding Test/Graph
단지번호 붙이기(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..