문제 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..
