인생 난제 알고리즘(13)
-
[백준] 미로 탐색 (BFS)
이번 문제는 BFS를 응용한 길찾기 문제에 대해 알아보자. 보통 미로 찾기 문제를 풀 때 BFS를 사용하는 이유는 DFS의 경우 도착지에 도달하지 못하는 경우, 무한 루프에 빠지지만 BFS는 큐의 아이템이 모두 빠져나가면 루프를 종료하기 때문에 도착 여부를 체크 할 수 있기 때문이다. #include #define MAX 101 #define INFI 999999 int Map[MAX][MAX]; typedef struct Queue { int x; int y; int s; } Queue; Queue Q[INFI]; int front = -1, rear = -1; void DFS (int maxY, int maxX) { // 왼, 오, 위, 아 int directX[] = {-1, 1, 0, 0}; in..
2019.10.04 -
[백준] 단지 번호 붙이기 (BFS)
바로 이어서 BFS로 풀어보자. BFS로 쉽게 풀 수 있었다. 코드는 아래와 같다. #include #define MAX 25 #define INFI 999999 int Map[MAX][MAX]; int SizeStorage[MAX * MAX]; typedef struct Queue { int x; int y; } Queue; Queue Q[INFI]; int front = -1, rear = -1; int BFS (int x, int y, int limit) { // 왼, 오, 위, 아 방향 계산 int sumSize = 1; int directX[] = {-1, 1, 0, 0}; int directY[] = {0, 0, -1, 1}; // 시작 지점 추가 rear++; Q[rear].x = x; Q[..
2019.10.03 -
[백준] 단지 번호 붙이기 (DFS)
이번에는 DFS / BFS 심화 문제를 풀어보도록 하자. 이 문제는 DFS와 BFS 두 가지 방법 모두 가능하며 이번 글에서는 DFS로 풀어보았다. 다음 글에서 동일한 문제를 BFS로 풀어보도록 하겠다. 이번 문제는 2차원 배열에서 이동 가능한 경로를 찾기 위해 상, 하, 좌, 우 모든 방향을 살펴 보는것이 핵심이다. 코드를 살펴보자. #include #define MAX 25 int Map[MAX][MAX]; int SizeStorage[MAX * MAX]; int DFS (int x, int y, int limit, int size) { // 왼, 오, 위, 아 방향 계산 int sumSize = size; int directX[] = {-1, 1, 0, 0}; int directY[] = {0, 0..
2019.10.03 -
[백준] DFS와 BFS
이 문제는 가장 기본적인 DFS / BFS 문제로 기본 개념만 알고있다면 쉽게 풀 수 있다. 성공한 코드를 먼저 확인해보자. #include #define MAX 1001 int metrix[MAX][MAX]; int visited[MAX * MAX]; void DFS (int v, int N) { // 정점 출력 printf("%d ", v); // 방문 표시 visited[v] = 1; // 인접 정점 체크 for (int d = 1; d 도착 정점 /= 도착 정점 -> 시작 정점) 이 성립되지 않으므로 대칭형태를 띄지 않는다. 이 경우에는 인접 행렬에서 값이 참일때만 정점간 이동을 수행한다.
2019.10.02 -
[SW Expert] BFS 문제 - 보급로
문제는 삼성 SW Expert 의 1249번 문제. 코드 유출하지 말라니까 문제는 직접 들어가서 보기를 권장한다. (다른 사람들은 다 올렸던데 ...) https://swexpertacademy.com/main/code/problem/problemDetail.do 짜증나는게 컴파일러가 C++ 밖에 없어서 어쩔수 없이 C 코드를 C++로 일부 바꿔서 작성하였다. 정답 코드는 아래와 같다. #include using namespace std; #define MAX 101 #define INFI 99999 typedef struct Queue { int x; int y; } Queue; int G[MAX][MAX]; int D[MAX][MAX]; Queue Q[9999999]; int front = -1; i..
2019.09.29