BFS

문제 풀이 1. 입력처리 res = [] for _ in range(int(input())): cnt = 0 m, n, k = map(int,input().split()) graph = [[0] * m for _ in range(n)] # 배추 입력 for _ in range(k): x, y = map(int,input().split()) graph[y][x]=1 for i in range(n): for j in range(m): if graph[i][j] == 1: graph[i][j]=0 bfs(i,j) cnt += 1 res.append(cnt) 2. 넓이 탐색 진행 que = deque() dx = [1,-1,0,0] dy = [0,0,1,-1] que.append((y,x)) while que:..

문제 풀이 조건 아기 상어의 처음 크기 : 2 먹이를 찾아 이동하는데 우선 방향은 상 -> 좌 아기 상어는 자기 크기 보다 작은 물고기만 먹을수 있음 하지만 같은 크기의 물고기 위치로는 이동할 수 있음 자신의 크기 만큼 수의 물고기를 먹으면 아기 상어의 크기는 +1 1. 입력 import sys from collections import deque input = sys.stdin.readline # 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다. # 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다. n = int(input()) graph = [] for _ in range(n): graph.append(list(map(int,input().split()..

문제 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다. 예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자. 2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 ..

문제 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 입력 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력..