Java

문제 Silver3 풀이 그래프 탐색(DFS)를 통해 인접 정점의 개수를 구하는 문제. 인접행렬을 boolean형으로 선언해 탐색하는 인덱스의 값이 true이고 visited배열이 false라면 탐색하며, 결과값 cnt 증가. 코드 더보기 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ static boolean[][] arr; static boolean[] visited; static int N, cnt; public static void main(String[] args) throws Exception{ BufferedReader br = ..

문제 Gold5 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 같은 색이 상하좌우 한곳이라도 인접해있으면 같은 area로 되므로, 깊이우선탐색을 통해 같은 구역을 확인한다. 문제에서 '같은 색상이 상하좌우로 인접해 있는 경우'라고 되어 있어서 상하좌우에 모두 인접해있어야 한다고 생각했었다...┗|｀O′|┛ 일반인이 보는 구역을 확인하기 위해 입력받은 배열 그대로 DFS를 돌린다. DFS를 돌리면서, 'G'색을 만나면 해당 인덱스에..

문제 Gold5 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀이 우선순위 큐(PriorityQueue) 활용 우선순위 큐란? 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 엘리먼트가 먼저 나가는 자료구조 문제에서는 강의가 가장 일찍 끝나는 강의실이 우선순위로 배정되어야 함(PriorityQueue Default) 강의의 start와 end를 int[]로 입력받아 저장.끝나는 시간을 기준으로 오름차 순 정렬.첫 번째 원소의 endTime을 큐에 먼..

문제 https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 풀이 알고리즘: 백트래킹, DFS 0행에서는 아무곳에서나 출발 할 수 있으므로 R길이만큼 돌며 깊이우선탐색 알고리즘을 실행한다. 탐색의 기저조건은 현재 Column이 마지막 Column일때. 그 외에는 삼방탐색을 하여 갈 곳을 정한다. 이 때, 지나온 곳은 'O'로 표시하여 다시 지나갈 수 없게 한다. 하나의 파이프라인이 만들어졌을 때(기저조건) 해당 칸에서 다시 탐색이 이루어지지 않도록 Flag를 사용한다..