안녕

0. 문제 링크 https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 1. 풀이 방법 우선 로봇 청소기에서 순열을 사용했던 것이 기억나서, 이번에는 조합을 이용하여 바이러스를 놔뒀다. 추가로 내가 얼만큼 공간을 채워야 하는지도 미리 파악했다. 만약 BFS가 끝났음에도 공간을 채우지 못했다면, -1을 출력하도록 처리했다. 2. 코드 import sys import itertools from collections import deque from copy impo..

0. 문제 링크 https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 www.acmicpc.net 1. 풀이 방법 원래 이거 BFS로 풀어야 하는데, BFS로 풀기 싫었다. 그래서 다른 방법으로 풀었다. 어떤 좌표를 기준으로 특정한 크기의 정사각형을 슬라이싱을 한 후에, 거기에 1(상어)이 있다면 그 거리 최대 거리가 되는 것 만약 상어가 없다면 크기를 한 칸 늘려서 또 슬라이싱을 한다. 그렇게 최대 거리를 갱신한다. 그리고 그 다음 번에는 아까 ..

0. 문제 링크 www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 1. 풀이 방법 단순 BFS를 하면 되는데, 추가로 내가 이미 방문한 곳보다 말을 적게 탔을 경우도 생각해봐야 한다. 또한 임계치보다 말을 적게 탔을 경우에는 말을 추가로 탈 수 있도록 처리함 아래에서 check 변수는 어느 지점까지 말을 탄 횟수이고, cur_k는 현재 내가 말을 탄 횟수 그 외엔 특별한 점 없음 2. 코드 import sys from collections im..

앞의 글을 읽으시면 이해에 도움이 됩니다. 2022.05.26 - [Computer Science/알고리즘] - [알고리즘 - 이론] The BackTracking Algorithm (되추적 알고리즘) [알고리즘 - 이론] The BackTracking Algorithm (되추적 알고리즘) 1. BackTracking 이란? Backtracking is used to solve problems in which a sequence of objects is chosen from a specified set so that the sequence satisfies some criterion 즉, 되추적 기술은 특정 집합에서 주어진 기준에 대로 원소의 순 hi-guten-tag.tistory.com 1. Bran..