문제 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 풀이 NxN 격자판에서 파이프를 한쪽 끝 (N, N)으로 이동시키는 방법의 수를 출력하는 문제이다. 파이프는 가로, 세로, 대각선으로 움직일 수 있으며 움직이는 각도는 45도이다. 즉 가로에서 세로, 세로에서 가로는 즉시 변환할 수 없다. 경우의 수를 계산하기 위해 아래와 같이 `DFS`로 풀었다. from sys import stdin def visitable(x, y, direction): if direction == DIA..
문제 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제 풀이 N개의 수가 차례대로 입력될 때, 중간 값을 출력하여 반환하는 문제이다. 문제를 풀기 위해서는 `heap`을 left, right로 나누고, left의 루트가 중간값이 되도록 로직을 구현하면 쉽게 해결할 수 있다. left는 최대 힙으로 만들고, right는 최소 힙으로 만들면 pop연산을 활용하기 좋다. 코드 from sys import stdin import heapq if __name__ == '__main__': n = i..
문제 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어�� www.acmicpc.net 문제 풀이 웜 바이러스가 하나의 네트워크 영역에서 퍼진다. 1번 컴퓨터부터 시작하여 웜 바이러스가 감염되는 컴퓨터의 개수를 반환하는 문제이다. 문제는 BFS/DFS 탐색을 통해 1번 노드로부터 탐색 가능한 영역을 찾는 문제이다. 초기에 입력되는 그래프의 정보를 양방향으로 기록하고 탐색을 진행하면 된다. 코드 from sys import stdin from collections import defaultdict, deque def bfs(start): q = ..
문제 16956번: 늑대와 양 크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 � www.acmicpc.net 문제 풀이 크기가 RxC인 목장이 있고, 양과 늑대가 목장 안에 있다. 울타리를 설치하여 늑대가 양에 접근할 수 없으면 1을 출력하고, 아닌 경우 0을 출력한다. 늑대가 양에 접근할 수 없는 경우는 늑대와 양이 인접해있지 않은 경우이다. 문제에서 최소 울타리 개수를 구하는 것이 아닌, 늑대가 양에 접근하지 못하도록 막으면 되므로 양을 기준으로 `상, 하, 좌, 우`로 울타리를 설치하면 문제를 해결할 수 있다. 코드 from sys import stdi..
문제 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람�� www.acmicpc.net 문제 풀이 N명이 한 줄로 서서 기다리고 있을 때, 볼 수 있는 사람의 수를 구하는 문제이다. 두 사람 A와 B가 서로 보기 위해서는 A, B 사이에 둘 보다 키가 큰 사람이 없어야 한다. 문제를 풀기 위해서는 `stack`을 활용하여, 현재 `top`보다 큰 키가 입력된다면, 이후에 입력되는 값은 현재의 `top`을 볼 수 없으므로 `pop`을 하여야 한다. 이와 반대의 경우 라면 `stack`에 추가한다. 주의해야 할 것은 연..
문제 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모� www.acmicpc.net 문제 풀이 문자열이 주어질 때, 폭발 문자열과 일치하는 부분이 있다면 제거가 가능하다. 문자열과 폭발 문자열이 일치하는 모든 부분을 제거하고, 남은 문자열을 반환한다. 만약, 남은 문자열이 없다면 FRULA를 반환한다. 이 문제는 전형적인 `stack`문제로 `stack`에 문자열을 하나씩 추가하면서, 폭발 문자열과 비교하여 제거 가능한지 파악 후에 제거하면 된다. 코드 from sys import stdin def solve(): stac..
문제 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 � www.acmicpc.net 문제 풀이 빙산의 높이가 주어질 때, 1년이 지날 때마다 바다에 인접한 수만큼 빙산이 녹아서 없어진다. 이때 빙산의 영역이 2개 이상이 되는 최소의 시간(년)을 찾는 문제이다. 문제를 풀기 위해서는 BFS를 통해 영역을 탐색함과 동시에, 각 빙하가 바다와 인접하고 있는 수를 카운트하여 해결할 수 있다. BFS를 통해, 빙하인 부분부터 탐색을 시작한다. 빙하 주위가 바다라면, 딕셔너리를 통해 해당 지점을 카운트한다. BFS 탐색 후에, 탐색 가능한 ..
문제 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치�� www.acmicpc.net 문제 풀이 NxN에 시험관에 바이러스들이 있을 때, 바이러스의 종류는 1부터 K까지 존재한다. 이때, 1번 바이러스부터 우선적으로 전염될 때, S초에 X, Y에 전염된 바이러스의 종류를 출력하는 문제이다. 초기에 전염되지 않은 곳은 0, 바이러스가 있는 곳은 1 ~ K 사이의 수로 표시된다. BFS를 통해 탐색하여 문제를 풀 수 있다. 최초에 주어진 시험관에서 바이러스의 종류를 찾고, 좌표를 기록한다. 1번 바이러스 부터 전..
