14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 접근한 방법 dfs를 이용한 조합과 bfs를 이용한 탐색을 이용한 문제입니다. 먼저 벽을 세울 3개의 자리를 순차적으로 구성해봐야 하므로 dfs를 이용해서 3개가 카운트될 때까지 빈칸을 찾아 진입합니다. 3개가 구성되면 bfs를 이용해 바이러스를 퍼트립니다. bfs를 여러번 동작해야 하므로 탐색을 시작할 때 미리 구성된 큐와 연구소 배열을 복사합니다. python에서는 큐는 deque의 copy, 어레이는 copy 라이브러리의 deepcopy를 이용하고 js에서는 어레이만 J..

1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 1707. 이분 그래프 접근한 방법 까다로운 테스트케이스, 조건들이 많아서 풀기에 꽤 재미있었던 문제. 이분그래프는 개념만 보면 한번에 이해하기 어려울 수 있는데 그림으로 표현하면 쉽습니다. 정점을 1 또는 0으로 표현했을 때 같은 집합 안에서 1과 1이 인접하거나 0과 0인 정점이 인접하는 경우가 없다면 이분그래프입니다. 이 그림에서는 왼쪽이 이분그래프, 오른쪽은 아닙니다. 이 아이디어 그대로 모든 정점을 1 또는 0으로 표시해놓을 표시용 배열(코드에서는 ma..

16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 16947. 서울 지하철 2호선 접근한 방법 그래프에 존재하는 사이클까지 각 노드가 도달가능한 최소 거리를 구하는 문제입니다. 두 가지 과정이 필요합니다. 1. 사이클 그래프 찾기 2. 사이클 그래프로부터 각 노드 도달거리 탐색하기 1번에서는 DFS로 사이클이 나올때까지 탐색합니다. 사이클을 찾는 방법은 탐색 출발 노드와 다음 탐색 노드가 같은 경우를 찾으면 됩니다. 단 사이클은 노드가 3개 이상이어야 하므로 깊이가 3회이상인 경우에만 ..

16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 16919. Two Dots 접근한 방법 DFS로 완전탐색합니다. 사이클을 확인하는 방법은 시작 점을 다시 되돌아올 경우이므로 이차원 배열로 모든 정점을 DFS로 탐색해서 탐색 경로가 4회 이상이면서 사이클이 만들어지는 경우를 찾습니다. Python import sys sys.stdin = open("input.txt", "r") # 제거 input = sys.stdin.readline n, m = map(int, input().split()) visit..

5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 5014. 스타트링크 접근한 방법 단순 조건 분할과 반복문으로 풀이합니다. 1. 현재 s값을 기준으로 목표층(target)보다 적을 때, - 위층을 더한 것이 전체층 이내라면 위층으로 간다. - 아래층을 뺀 것이 전체층 이내라면 아래층으로 간다. 2. 현재 s값을 기준으로 목표층보다 클 때, - 아래층을 뺀 것이 전체층 이내라면 아래층으로 간다. - 위층을 더한 것이 전체층 이내라면 위층으로 간다. 예를 들면 s가 9, target이 10, u = 2, d = 1 와 같은 ..

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 7576. 토마토 접근한 방법 인접한 토마토부터 확인해야하니 BFS로 접근해야 하지만 익은 토마토가 여러개 분포하는 경우가 문제입니다. 큐를 2개 사용하여 해결했습니다. 우선 주어진 배열에서 익은 토마토를 모두 체크하여 큐1에 넣고 큐2는 빈 큐로 만들어줍니다. BFS로 진입하여 현재 큐1에 들어있는 익은 토마토의 상하좌우를 모두 체크해 큐2에 넣어줍니다. 큐1에 넣지 않는 이유는 무한 루프를 돌지 않기 위해서입니다. 다음번 루프에서는 현재 큐가..