📝 알고리즘/GraphTraversal

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

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

문제 Silver1 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 사방탐색 중 깊이우선탐색(DFS)를 사용하여 해결 기본 DFS코드에 단지 내 집의 수를 저장 할 cnt배열을 추가하였다. 따로 배열을 만들어 준 이유는 마지막에 sort를 해야하기 때문. 코드 더보기 import java.io.*; import java.util.*; public class Main{ static int N, idx; static int[][] arr; st..

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