2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net ✏️ 풀이 가장 먼 거리를 구하는것이 이 문제의 핵심이였다. 하지만 한 지점에서만 구하는 것이 아니라 L있는 부분에서 가장 먼거리라서 2중 for문을 통해서 브루트 포스를 통해서 모든 거리를 구해 그중에 가장 먼 거리를 출력하는 것이다. 이번 문제는 c++를 익히기 위해서 두가지 언어로 풀었다. 처음에는 파이썬으로 풀어서 해결방법을 찾고, 그걸 바탕으로 c++을 이용해서 코드를 작성했다. 💻 코드 import sys from collections import deq..
25418번: 정수 a를 k로 만들기 7(A), 8(연산 1), 9(연산 1), 18(연산 2), 19(연산 1), 38(연산 2), 76(연산 2), 77(연산 1)이 최소 연산이므로 정답은 7이다. www.acmicpc.net ✏️ 풀이 입력으로 a, k가 주어지는데 그냥 a를 k로 만드는 최소 연산 횟수를 출력하는 것이다. 최소, 최단 이런 단어가 보이면 이제는 바로 BFS로 풀면 되겠다는 생각을 한다. 뭐 아닐 수 도 있겠지만, 그건 많이 풀어보면 BFS구나, 아니구나를 판단할 수 있을 것이라고 믿는다. 큐에는 시작과 연산 횟수를 넣었다. 그렇게 연산을 하면 cnt를 증가 시키고, k에 도달하면 출력을 하고 끝을 낸다. BFS의 개념만 알면 금방 풀 수 있는 문제라서 쉽게 풀 수 있었다. 💻 코드..
2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net ✏️ 풀이 입력으로는 k개의 영역을 준다. 그래서 나는 x1, y1, x2, y2로 입력을 받았다. 이렇게 입력을 받아서 previsit으로 입력받은 영역을 방문 처리했다. 간단하게 표현하면 미로에서 벽을 세운 느낌으로 처리했다. 그리고 BFS를 통해서 영역의 너비를 계산했다. 이문제에서는 처음 입력받은 좌표에 해당하는 구역만큼만 방문 처리를 했으면 금방 풀 수 있는 문제였다. BFS는 평소에 풀던 다른 문제처럼 처리를 하면 되는 거여서 금방..
16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 이 문제를 풀면서 어떻게 BFS를 통해서 최소 탐색을 할 지 고민을 했습니다. 그래서 1~6을 추가해가면서 100이 되는 것을 확인해야한다고 생각했는데, 어떻게 풀어 나갈지가 가장 문제였다. 기존과 비슷하게 BFS를 진행하고, 각 경우의 수를 나누어 풀어나갔다. import sys from collections import deque input = sys.stdin.readline def bfs(start): q = ..
7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 앞에서 풀었던 토마토 문제와 같은 방법으로 BFS를 사용해서 풀면 쉽게 풀 수 있었다. 대신 2차원이 아닌 3차원 배열이라서 H의 값을 더 추가해서 풀었다. 코드는 앞에서 풀었던 BFS와 똑같지만 matrix의 차원만 하나 더 추가된 방법으로 풀었다. 그래서 쉽게 풀 수 있었다. import sys from collections import deque input = sys.stdin.readline directions = [(1, 0, 0..
7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 최소라는 단어를 보고 바로 BFS를 사용한다는 것을 알았다. 그렇게 처음에는 BFS를 활용해서 풀었는데 생각해보니 한 곳에서 시작한 첫 포인트가 토마토 전체를 익은 상태로 만들어 더 많은 일 수가 나왔다. 시작점이 동시에 출발해야하는 것을 깨닫고, 이번 알고리즘2 수업에서 들은 Multi Source BFS를 떠올려서 queue에 시작점을 넣어 탐색하게 만들었다. 그렇게 푸니 최소 일수가 나온것이다. import sys from collectio..
7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 처음 이문제를 풀었는데 계속 답이 나오지 않았다. matrix를 출력해보니 한 방향으로 가지 않는 것이였다. 그래서 살펴보니 directions의 배열에 잘못 입력을 해서 문제였다. 배열을 잘 고쳐서 8방향 전부 갈 수 있게 만들어 풀 수 있었다. import sys from collections import deque input = sys.stdin.readline directions = [(-2, -1), (-1, -2), (2, 1), (1, 2), (-2,..
1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 이 문제는 상하좌우를 탐색하면서 연결된 컴포넌트를 다 이어서 그 연결된 컴포넌트가 몇 개인지 구하면 되는 문제였다. 저번에 푼 바이러스문제와 비슷해서 금방 풀 수 있었다. import sys from collections import deque input = sys.stdin.readline directions = [(-1, 0), (0, -1), (1, 0), (0, 1)] def bfs(x, y, matrix): queue = deque([(x, y)]) matrix[x..
