문제 https://www.acmicpc.net/problem/17129 17129번: 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 첫째 줄에 정보섬 2층의 크기 n과 m이 주어진다. (1 ≤ n,m ≤ 3000, 4 ≤ n×m ≤ 9×106) 이후 n행 m열에 걸쳐 0, 1, 2, 3, 4, 5로만 구성된 Ai,j가 주어진다. Ai,j와 Ai,j+1사이에 공백은 주어지지 않는다. 2, www.acmicpc.net 풀이 처음에는 모든 거리를 다 구한뒤, 3,4,5까지의 거리가 모두 -1인 경우만 NIE를 출력했고 이외의 경우에는 -1을 제외하고 최솟값을 구해주었다.. 근데 어차피 BFS는 근처에 있는거 먼저가니까 BFS하는 와중에 3,4,5를 만나면 믿음을 가지고 chk 변수를 두어보았더니 성공했다. ..

문제 https://www.acmicpc.net/problem/1245 1245번: 농장 관리 첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 풀이 BFS로 풀었다. 우선 전체 배열을 탐색하며 방문한 적이 없다면 제일 높은 건지 확인하기 위해 해당 위치에서 BFS를 시작한다. check라는 변수를 통해 인접 지역 중 해당 위치가 가장 높을지 안높을지 체크한다. 높으면 0, 안높으면 1을 반환했다. 큐에 해당 위치를 넣어주고, 8개를 돌며 인접한 곳을 모두 탐색하는데 이때 다음 탐색할 곳의 높이가 현재 ..

문제 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 풀이 1. 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다.라는 조건을 잘봐야한다. 큐에 들어갈 때 바이러스 번호를 기준으로 정렬을 한 다음 넣어주면 매 초마다 큐에 바이러스 번호가 작은 순서대로 남게 된다. 그리고 매 초마다 큐에 들어오는 칸 수만큼 반복해서 상하좌우 검사를 해준다. 이 문제를 예시로 - 맨 처음에는 3개의 바이러스가 큐 안에 들어있다..

문제 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 기본 BFS 문제이다. 상하좌우가 아닌, 나이트가 이동할 수 있는 좌표를 탐색한다. dx,dy만 잘 설정해주면 된다. 거리를 계산해서 배열에 저장하고, 목적지에 저장된 거리를 출력하면 된다. 코드 import sys from collections import deque read = sys.stdin.readline T = int(read()) dx = [2,1,-1,-2,-2,-1,1,2..

문제 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 풀이 이 문제도 BFS의 기본 문제. 아무래도 C++과 자바로 풀었던 문제라 쉽다고 생각했는데 vis를 Boolean으로 선언해놓고 0이냐 아니냐로 비교했더니 오류나서 한참 고생... BFS를 함수로 선언한 코드가 많던데, 난 중복이 없길래 그냥 ... 풀어서 썼다. 이중 for문을 통해서 BFS 탐색을 시작할 위치를 고르고, 그림의 수를 카운팅해준다. 그리고 면적은 큐에 들어온 좌표 수 만큼 카..

문제가 상당히 길다. 하지만 이전 문제들처럼 그냥 거리계산만 하면 된다. 기본 BFS문제에 속하는 문제이다. 맵의 시작 부분을 큐에 넣음과 동시에 BFS를 시작한다. 도달하지 않은 곳의 dist 값은 -1이고, 시작점으로부터의 거리가 dist 값에 업데이트된다. 생각해 주어야 할 것은, (n-1,m-1)번째 dist값이 -1이라면 길이 막혀서 갈 수 없는 곳이므로 -1을 출력한다는 것과, 시작점의 dist을 0으로 설정하였으므로 마지막에 값을 저장할 때 +1을 해줘야한다는 것이다. #include #include #include using namespace std; int dist[102][102]; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; int solution(v..

BFS와, DFS의 가장 기본적인 문제인듯 싶다. dfs는 재귀함수로 구현하였고, bfs는 큐를 사용하였다. 먼저 DFS의 경우, 그래프에서 노드간의 연결을 위해 벡터를 사용하였다. 그냥 이차원 배열을 사용해도 좋을 듯 하다. 입력 받으며 벡터에 저장할 때, 해당 그래프가 양방향임을 주의하자 "단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문" 이라는 문구로 인해 sort가 필수적이다. 그러나 2차원 배열을 통해 1번 노드부터 m번 노드까지 방문하면서 1. 방문한 적이 있는지, 2. x번쨰와 i번째가 연결되어 있는지 확인하는 방식을 사용해도 좋을 듯하다. 다음으로 BFS의 경우, 우선 시작 노드에 방문 표시를 한 뒤, 큐에 푸시한다. 그리고 큐가 빌때 까지 무한 루프 내부..

www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net BFS를 통해 문제를 해결했다. 주의할 점 2가지가 있는데 1. 가로, 세로 인덱스가 반대로 되어 있다. 2. 각 테스트 케이스마다 보드를 초기화 해 주어야 한다. 나는 1, 2번으로 인해 시간을 굉장히 오래 잡아먹었다. 다른 요소들은 그냥 보통의 BFS에 count를 더한 것이다. #include #include using namespace std; #define X first #define Y second int n,m..

www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net BFS 문제 입력을 string으로 받는다. 한 칸씩 이동할 때마다 카운트를 하며 맨 처음 시작부터 각 칸까지의 거리를 저장한다. #include #include #include using namespace std; string board[102]; int dist[102][102]; int dx[4]={1,0,-1,0}; int dy[4]={0,1,0,-1}; int main(void){ ios_base::sync_with_stdio(0);..

www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 기초적인 BFS문제입니다. 제가 전부 생각해 낸게 아니라 기초 알고리즘을 비롯해 문제에 대한 도움을 받고 이 문제를 풀었습니다. 아래에 출처를 표시했습니다. 우선 board와 방문 표시를 위한 visit 배열을 선언하고, 각 칸의 상하 좌우를 살피기 위해 dx, dy를 선언했습니다. 우선 가장 먼저 방문하는 곳을 (x,y)라고 정했습니다. 이후 아래(x+1,y), 오른쪽(x,y+1), 위(x-1,y), 왼쪽(x,y-..