알고리즘

문제 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 풀이 전형적인 BFS 시뮬레이션 문제! 모든 로직의 순서와 불이 번지는 과정만 꼼꼼히 작성해주면 된다. BFS 로직 순서 1. Depth가 늘어날 때 마다 불 확산 2. 가려는 길에 불이 있으면 Continue 3. 종료 조건 확인 4. 상근이 이동 가능 경로 탐색 불이 번지는 과정 1. 불이 새로 번진 곳을 저장할 리스트 선언 2. 현재 불 리스트를 돌며 새로 번진 리스트에 추가 3. 현재 불 리스트를..

문제 풀이 단순히 win-lose 개수와 무승부 개수만 맞추면 된다고 생각했다면 바로 실패 1. 가능한 매치들을 모두 살펴 보아야 함: A - B,C,D,E,F / B-C,D,E,F / C-D,E,F / D-E,F / E-F 2. 매치를 돌며 승-패 / 무-무 / 패-승 의 경우를 살펴봄 3. 재귀가 15회(총 경기 횟수)돈 경우: 유효한 경기 결과! 코드 더보기 import java.util.*; import java.io.*; public class Main { static final int T = 4; // 테스트 케이스 수 static int[][] game; static int[][] match = new int[15][2]; // A-BCDEF / B-CDEF ... 저장 static bool..

문제 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/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 풀이 시작점에서 모든 정점까지의 최단경로를 구하는 다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘 구현 - 시작점에서부터 방문여부와 시작점부터의 최소 경로 정점을 탐색 - 최소 경로 정점 탐색 후, 해당 정점에 대한 distance배열(해당 정점을 경유해서 갈 수 있는 최단 거리)을 재설정 그래프 정보를 처음 인접행렬로 풀었으나 테케의 크기가 매..