기록

문제 보기 BFS 문제이다. 연구소의 모든 빈칸에 바이러스가 있게 되는 최소 시간을 구하면 된다. 바이러스 후보 위치 파악 모든 빈칸에 바이러스가 있도록 하기 위해서는 바이러스를 놓을 수 있는 위치를 구해야 한다. 따라서 2차원 배열을 탐색하면서 값이 2인 곳의 위치를 따로 저장한다. 조합을 활용하여 모든 경로 탐색 바이러스는 후보 위치 중 최대 m개까지 놓을 수 있다. 파이썬은 itertools의 combination을 통해서 후보 위치 중 m개를 놓는 모든 경우를 쉽게 파악할 수 있다. BFS를 이용한 탐색 최종적으로 선택된 바이러스는 상, 하, 좌, 우를 탐색하면서 퍼져나간다. 모든 경우에 대해서 bfs 탐색을 진행한 후 가장 적은 시간에 모든 빈칸에 바이러스를 퍼트린 시간을 출력하면 된다. 만약 ..

문제 보기 구현, 시뮬레이션 문제이다. 턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 게임이 종료되며, 게임이 종료되는 턴의 번호를 출력하면 된다. A번 말이 이동하려는 칸은 흰색, 빨간색, 파란색, 체스판을 벗어나는 경우 중에 하나이다. 체스판을 벗어나는 경우는 파란색과 동일하기 때문에 총 3가지 경우가 존재한다. 따라서 3가지 연산을 구현하면 된다. 말의 이동을 관리하기 위해서 2차원 배열을 선언하였다. 만약 해당 칸에 말이 없다면 빈 공간 형태이며, 말이 2마리 있다면 첫 번째 말, 두 번째 말 순서로 쌓인 형태이다. 흰색과 빨간색 칸 연산은 매우 유사하며 말을 쌓는 순서만 바꾸면 된다. 전체적인 연산 순서는 아래와 같다. 1. 현재 칸에서 이동하려는 말의 인덱스를 파악한다. (현재 칸에 A, B..

문제 보기 브루트포스, 구현, 시뮬레이션 문제이다. 선거구를 나누는 방법 중에서, 인구가 가장 많은 선거구와 가장 적은 선거구의 인구 차이의 최솟값을 구하면 된다. 브루트포스를 구현하기 위해서는 1번 조건에 맞는 x, y, d1, d2 값이 필요하다. 1번 조건: d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N x, y, d1, d2는 1 이상 n이하이기 때문에 밑줄 친 부분의 조건만 추가하면 1번 조건을 만족한다. 추가적으로 2번 경계선 조건에 해당하는 위치에 5를 대입하고, 선거구를 구별하면 된다. 경계선 조건과 선거구 구별 또한 문제에서 주어진 조건을 그대로 코드로 작성하면 된다. 코드 import copy INF = 1e9 def solve(x..

문제 보기 DFS, 구현, 시뮬레이션 문제이다. 원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구하면 된다. 원판 돌리기에서 필요한 연산은 2가지이다. 1. 원판 회전 2. 인접하면서 같은 수를 지우기 원판 회전은 시계 방향, 반시계 방향으로 나눠서 구현하였다. 시계 방향은 array[i] = [array[i][-1]] + array[i][:-1]로 구현하였다. 마지막 값을 제일 앞으로 옮겼다. 반시계 방향은 array[i] = array[i][1:] + [array[i][0]]로 구현하였다. 첫 번째 값을 마지막 위치로 옮겼다. 인접하면서 같은 수 지우는 연산은 dfs로 구현하였다, 현재 위치의 상, 하, 좌, 우에 현재 위치에 있는 값이랑 같은 값이 있으면 계속해서 탐색하도록 하였다. 예를 들어 현..

문제 보기 백트래킹 문제이다. 주사위에서 나올 수 10개를 미리 알고 있을 때, 얻을 수 있는 점수의 최댓값을 구하면 된다. 주사위 윷놀이 문제는 모든 경로를 해보기 전까지는 어떤 경로가 최댓값을 가지는 지 판단할 수 없다. 따라서 모든 경로를 탐색하면서 조건을 통해 시간을 단축하는 백트랙킹 알고리즘을 구현하고자 하였다. 경로는 크게 4가지로 나눌 수 있다. 1. 바깥쪽으로만 도는 경우 2. [10]을 지나는 경우 3. [20]을 지나는 경우 4. [30]을 지나는 경우 말이 겹치는 경우는 아래와 같다. - 2, 3, 4 경로는 [25] ~ [40] 사이의 경로에서 말이 겹칠 수 있다. - 1 경로는 [10, 20, 30, 40] 위치에서 다른 말과 겹칠 수 있다. 말이 얻을 수 있는 최대 점수는 40점..

문제 보기 구현, 시뮬레이션 문제이다. 초록색 보드와 파란색 보드를 관리하는 두 배열(6x4, 4x6)을 선언하고 주어진 블록을 하나씩 처리하면 된다. 1 x 1 블록은 0, 1 x 2 블록은 1, -1, 2 x 1 블록은 2, -2 값으로 서로 연관이 있음을 표현하였다. 만약 연관 있는 블록에서 1칸이 사라지는 경우에는 남은 칸의 값을 0으로 업데이트하였다. 전체적인 알고리즘 수행 과정은 아래와 같다. 1. 블록 놓기 2. 꽉 찬 행, 열처리 3. 빈 공간 처리 4. 0 ~ 1 행 처리 순으로 진행된다. 하나의 블록에 대해서 2 ~ 4 과정을 한 번만 수행하는 것이 아니라 더 이상 바뀌는 부분이 없을 때까지 반복하였다. 코드 import sys sys.setrecursionlimit(10 ** 9) d..

문제 보기 BFS + 우선순위 큐를 활용하여 구현하였다. 맵이 주어졌을 대, 최단 경로를 구하는 것이 최종 목표이다. 벽을 부술 수 없으면 간단한 BFS 구현 문제이지만 벽을 1개 부술 수 있다는 것이 핵심이었다. (0, 0)에서 중간 지점(4, 4)에 도달하는 방법이 2가지가 있을 때(벽을 부수고 왔을 때, 벽을 부수지 않고 왔을 때) 이 2가지 방법을 동일하게 생각하면 안 된다. 이후에 또 벽을 만나는 경우에 결괏값이 다르기 때문이다. 따라서 벽에 따른 방문 체크를 따로 관리하였다. 우선순위 큐는 거리가 제일 짧은 경로들을 계속적으로 업데이트하여 목표 지점에 도달하기 위해서 사용하였다. 알고리즘 설계는 아래와 같다. 1. (1, 0, 0, 0)를 우선순위 큐에 삽입한다. (거리, 좌표, 벽 플래그) ..

문제 보기 이 문제는 플로이드-워셜 문제이다. 여행이 가능한 지 확인하기 위해서는 모든 경로에 대한 정보가 필요하다. 플로이드-워셜을 사용하면 모든 도시 사이의 거리를 구할 수 있다. 플로이드-워셜 알고리즘은 3중 for문을 통해 쉽게 구현할 수 있다. 플로이드-워셜을 통해서 모든 도시 사이의 거리를 구한 후 여행을 하면서 만약 해당 지점에 도착할 수 없으면 NO를 출력하였다. * 자기 자신에게 여행을 가는 경우도 있다! 코드 if __name__ == "__main__": n = int(input()) # 총 도시의 수 m = int(input()) # 여행 계획에 속한 도시들의 수 graph = [list(map(int, input().split())) for _ in range(n)] move = ..

문제 보기 이 문제는 그리디(다익스트라) 문제이다. 주유소에서 멈추는 횟수를 최소화하는 문제이다. 현재 위치에서 갈 수 있는 곳 중 연료의 양이 가장 많은 곳을 방문하면 된다. 즉 그리디 방식으로 풀면 된다. 그리디 방식으로 정답을 구하는 것 자체는 어렵지 않았지만 제한 시간을 고려하면서 구현하기는 어려웠다. 시간제한을 해결하기 위해 현재 위치에서 갈 수 있는 곳은 우선순위 큐에 (-비용, 거리) 형태로 우선순위 큐에 삽입하였고, 갈 수 없는 곳은 (거리, -비용) 형태로 삽입하였다. 즉 갈 수 있는 곳은 비용 내림차순으로 정렬된 우선순위 큐이며, 갈 수 없는 곳은 거리 오름차순으로 정렬된 우선순위 큐 형태이다. 갈 수 없는 곳을 (-비용, 거리) 순으로 삽입하면 비용이 높은 곳부터 탐색하지만 (거리, ..

문제 보기 이 문제는 최소 신장 트리(Minimum Spanning Tree) 문제이다. 두 마을로 분리하기 위해서 먼저 최소 신장 트리를 구현하고, 최소 신장 트리를 구성하는 간선 중에 비용이 가장 높은 간선을 제거하였다. 위 과정을 구현하기 위해서 크루스칼 알고리즘을 사용하였다. 1. 입력 받은 간선을 비용을 기준으로 내림차순 정렬을 한다. 2. 비용이 낮은 간선부터 사이클 여부를 확인하고 사이클이 발생하지 않으면 삽입한다. 3. 모든 간선에 대해서 위 과정을 수행한 후 제일 마지막에 삽입한 간선을 제거하였다. 코드 def find_parent(x): if parent[x] != x: parent[x] = find_parent(parent[x]) return parent[x] def union_par..