1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net DP문제를 잘 몰라서 처음에는 8까지 모든 경우의 수를 적었다. 적고 보니 어떻게 풀어야할 지 보여서 쉽게 풀 수 있다. 3이나 2로 나눠지면 best를 업데이트를 했다. 최소값만 넣을 수 있게 min을 활용해서 풀고, 마지막에 append하기 전에 min값을 넣었다. 이렇게 풀고 성공(832ms)은 했는데 생각을 해보니 굳이 인덱스를 넣을 필요가 없다는 것을 알게 되었다. import sys input = sys.stdin.readline num = int(input()) memo = [(0,0), (1,0)] for i in range(2, num+1): best = 99..
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..
2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 바이러스 문제는 DFS와 BFS를 활용해서 풀 수 있는 간단한 문제입니다. 알고리즘2 수강하면서 풀다보니 CC(Connected Component)배우면서 유형이 비슷하다고 생각했습니다. # 바이러스 # https://www.acmicpc.net/problem/2606 import sys from collections import deque input = sys.stdin.readline def bfs(graph, visited, node): queue = deque..
