1. 문제 출처 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 2. 풀이 BFS를 이용하지만 벽을 부수는 경우가 있기 때문에 데이크스트라 알고리즘도 같이 이용해야 한다. 벽부시는 것을 가중치로 두고 만약 벽을 부수지 않고 이동한다면, 가중치를 더해주지 않는 것이 필요하다. 다음과 같이 진행된다. 1. 상하좌우 중 범위를 나가지 않는 곳으로 이동 2. 해당 이동좌표에 벽이 있다면 전 가중치+1 을 해주고 append를 통..
1. 문제 출처 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 2. 풀이 DFS 와 BFS 에 대한 기초적인 문제를 확인 할 수 있었다. # 필요 라이브러리 불러오가 import copy from collections import deque # 입력 n, m, v = map(int, input().split()) # 그래프 값 초기화 graph = [[0 for _ in range(n)] for _ in ..
1. 문제 출처 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 2. 풀이 단순 bfs알고리즘을 사용하는 문제이다.. # 입력받기 n,m = map(int,input().split()) # 미로 maze = [] # 상하 좌우 이동 범위 dx = [0,0,-1,1] dy = [-1,1,0,0] # 입력 받기 for i in range(n): maze.append(list(map(int,list(input())))) # bfs를 사용하여 문제를 해결하였다.. def soluti..
1. 문제 출처 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 2. 풀이 간단한 bfs문제이다. from collections import deque # 입력 m,n,k = map(int,input().split()) # 상하좌우 이동 dx = [0,0,-1,1] dy = [-1,1,0,0] # 방문 리스트 visted = [[0]*m for _ in range(n)] # 너비 리스트 area_list = [] # 직사각형..
1. 문제 출처 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 2. 풀이 기초적인 BFS문제 이지만 , 가로 세로가 리스트에서는 [세로][가로]로 되어있어 헷갈렸었다... 조심하자. from collections import deque # 테스트 케이스 개수 t = int(input()) # 이동 경로(상하좌우) dx = [0,0,-1,1] dy = [-1,1,0,0] for _ in range(t): # 팔요 벌레 개수 worm = 0 # 가로,세로,배..
1. 문제 출처 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 2. 풀이 매번 이동시에 bfs를 이용하여 각 지점의 최소 거리를 구하고 이동하는 작업을 더 이상 이동할 수 있는 거리에 먹이가 없을 때 까지 반복한다... from copy import deepcopy from collections import deque # 입력 n = int(input()) space= [0] * n for i in range(n): space[i] =..
1. 문제 출처 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 2. 풀이 연구소 문제와 비슷한 점이 있다. 연합하고 인구를 이동 시켜주는 작업을 BFS를 사용하여 구현하고 연합체의 개수가 전체 데이터의 수와 같으면 반복 했던 횟수를 반환한다... from collections import deque # 입력 N,L,R = map(int, input().split()) A = [] for _ in range(N): A.append..
1. 문제 출처 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 2. 풀이 해당 문제는 1 ->2->....->K 순으로 바이러스가 움직이기 때문에 2차원 리스트을 queue처럼 이용하고자 하였으나, 그것보다 temp라는 3차원 배열에 코드와 같이 index + 1 과 같은 바이러스 번호를 가진 좌표를 모으고 2차원으로 펴준 queue를 생성한다. 그러면 자동적으로 바이러스 번호가 작은 순으로 나오게 된다. 예시)..
