📌 Intro 그래프 탐색의 기본은 BFS와 DFS다. 그 중 BFS에 대해 알아보도록 하자. 📌 BFS(너비 우선 탐색) BFS란 Breadth-First Search로 너비 우선 탐색을 말하며 시작 노드로부터 인접한 노드를 먼저 탐색하고 멀리 떨어져있는 노드를 가장 나중에 방문하는 방법이다. 보통 BFS는 두 노드 사이의 최단 경로를 구할 때나 임의의 경로를 찾고 싶을 때 많이 사용한다. BFS는 자료구조 큐(Qeueu)를 이용하여 구현할 수 있다. 인접 리스트로 표현된 그래프의 경우 시간 복잡도는 O(N+E)가 된다. 인접 행렬로 표현된 그래프의 경우 시간 복잡도는 O(N^2)이 된다. 간선의 숫자가 적다면 인접 행렬보다 인접 리스트를 사용하는 것이 시간상 유리하다. STEP 0 다음과 같은 그래프..
📌 Intro 그래프 탐색의 기본은 BFS와 DFS다. 그 중 DFS에 대해 알아보도록 하자. 📌 DFS(깊이 우선 탐색) DFS는 Depth-First Search로 깊이 우선 탐색이다. 시작 노드로부터 계속 갈 수 있을 때까지 탐색을 진행하다 갈 수 없게되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 탐색을 진행하는 방법이다. 모든 노드를 방문하고자 하는 경우 DFS를 사용하는데 이전에 다루었던 BFS보다 구현 방법이 간단하지만 단순 검색 속도 자체로만 보면 BFS가 더 빠르다. DFS를 구현하기 위해서는 스택(Stack)이라는 자료구조를 사용한다. DFS의 동작 과정은 다음과 같다. 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인..
📌 Intro 이전에 정리했던 다익스트라 알고리즘은 "한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우"에 사용할 수 있는 최단 경로 알고리즘이다. 하지만 이번에 살펴볼 플로이드 워셜 알고리즘은 "모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우"에 사용하는 알고리즘이다. 📌 Floyd-Warshall Algorithm 다익스트라 알고리즘은 매 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다. 그리고 해당 노드를 거쳐 가는 과정을 진행하면서 최단 경로 리스트를 수정해나간다. 그리고 이 때 방문한 노드인지 확인하는 과정을 거친다. 하지만 플로이드 워셜 알고리즘은 노드를 방문할 때 방문한 노드인지 아닌지 확인할 필요가 없이 모든 노드에 대해서 동작하는 알고리..
📌 Intro 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다. 최단 경로를 찾기 위한 알고리즘은 여러 종류가 있는데 그 중에서 가장 많이 사용되는 다익스트라 알고리즘에 대해 알아보도록 하자. 📌 Dijkstra Algorithm 다익스트라 알고리즘은 한 노드에서 다른 모든 노드까지의 최단 경로를 구하는데 주로 사용한다. 즉 한 지점으로부터 다른 모든 지점까지 각각의 최단경로를 구할 수 있게 되는 것이다. 다익스트라 알고리즘을 사용하기 위해서는 모든 간선의 가중치가 음이 아니어야 한다는 조건이 있다. 다익스트라 알고리즘은 기본적으로 그리디 알고리즘으로 분류되는데, 매번 "가장 비용이 적은 노드"를 선택하기 때문이다. 알고리즘에 대해 간략하게 정리하면 다음과 같다. 출발 노드를 설정한다. 최단 거..
문제링크 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 문제 풀이 시간의 순서대로 격자판의 상태를 나열하면 다음과 같다. 0초 : 초기상태 1초 : 초기상태와 동일(봄버맨이 아무것도 하지 않음) 2초 : 폭탄이 설치되어 있지 않은 모든 칸에 폭탄 설치 3초 : 0초에 설치되어 있던 폭탄이 폭발(폭발한 뒤의 격자판을 board_3이라고 가정) 4초 : board_3 격자판에 폭탄이 설치되어 있지 않은 모든 칸에 폭탄 설치 5초 : 2초에 설치한 폭탄이 폭발(폭발한 뒤의 격자판을 board_5라고 가정) 6초 : board_5 격..
문제 링크 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 설명 바로 이전에 풀었던 문제와 연결되는 문제다. 단지 2차원에서 3차원으로 차원이 늘어난 것이 차이점이다. 간단하게 정리를 다시 해보면 토마토 농장의 상태가 주어지고 모든 토마토가 익을 때까지 필요한 날짜를 출력해야한다. 만약 처음부터 모든 토마토가 익어있는 상태라면 0을 출력하고, 토마토가 익지 못하는 상태라면 -1을 출력해야 한다. 토마토가 익기 위해서는 익은 토마토와 인접해야만 하고 여기서 인접하다는 것은 위, 아래..
문제 링크 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 설명 토마토 농장의 현재 상태가 주어지고 모든 토마토가 익을 때까지 필요한 날짜를 출력해야 한다. 만약 모든 토마토가 익어있는 상태라면 0을 출력하고, 토마토가 익지 못하는 상태면 -1을 출력해야 한다. 토마토가 익기 위해서는 익은 토마토와 인접해야만 한다.(다른 경우는 없다.) 여기서 인접해야 한다는 말의 의미는 상, 하, 좌, 우로 인접해야 한다는 것이다.(대각선은 안된다.) 문제 풀이 bfs를 사용하여 풀이할 수 있는 문제다..
문제 링크 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 설명 주어진 미로의 (1, 1)의 위치부터 (N, M)의 위치까지 이동할 때 지나야 하는 최소의 칸 수를 구해야 한다. 문제 풀이 시작 지점에서 도착 지점으로 지나야 하는 최소의 칸 수를 출력해야 하기 때문에 이 문제는 BFS로 해결할 수 있다. 보통 최소 거리는 모두 BFS로 해결하는 것 같다. 다른 칸으로 이동할 때는 서로 인접한 칸으로만 이동이 가능하다. 즉 상, 하, 좌, 우 로만 이동이 가능한 것이다. 아래 코드에서 보면 알겠지만 그것을 조금 더 쉽게 사용하기 위해 크..
