Total

[2468] 안전영역(DFS)

2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net import sys sys.setrecursionlimit(10**6) input=sys.stdin.readline # 네 방향 탐색을 위한 상수 → ↓ ← ↑ dr=[0,1,0,-1] dc=[1,0,-1,0] n=int(input()) graph=[list(map(int, input().split())) for _ in range(n)] # print(graph) def DFS(i,j,h): visited[i][j]=True for d in range(4): next..

[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..

사과나무(BFS, 격자탐색, 다이아몬드)

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

송아지 찾기(BFS : 상태트리탐색)

분석 풀이 """ 현수의 위치와 송아 지의 위치가 직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 앞으로 1, 뒤로 1, 앞으로 5를 이동. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 첫 번째 줄에 현수의 위치 S와 송아지의 위치 E, 직선의 좌표 점은 1부터 10,000 까지이다. 5 14 3 """ from collections import deque s,e=map(int, input().split()) # 출발점, 도착점 max=10000 # 좌표 최댓값 visited = [False]*(max+1) visited[s]=True # 시작점 방문 dist=[0]*(max+1) dist[s]=0 queue = deque() queue.append(s) while ..