너비우선탐색

DFS & BFS

DFS(Depth First Search) • 깊이 우선 탐색 • 스택 or 재귀함수 이용 • 동작 과정 1. 탐색 시작 노드를 스택에 넣고 방문 처리 2. 스택의 최상단 노드에 방문하지 않은 노드가 하나라도 있다면 그 노드를 스택에 넣고 방문 처리 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드 꺼냄 3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복 BFS(Breadth First Search) • 너비 우선 탐색 • 그래프에서 가까운 노드부터 우선적으로 탐색 • 큐 사용 • 특정 경로에서 최단거리 찾을 때 많이 사용 • 동작 과정 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리 2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리..

[1707] 이분 그래프(C++)

문제 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 내 코드 // [1707] 이분 그래프 // https://www.acmicpc.net/problem/1707 // 그래프, dfs, bfs #include #include #include #include using namespace std; vector list[200001]; int visited[200001], v; bool ans = true; void bipartite(int start) { queue q; visited[start] = 1; q...

[10451] 순열 사이클(C++)

문제 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 해결 방법 계속 런타임 에러가 떠서 for문이 너무 많은건가.... 변수형을 잘못 선언했나..... 한참을 찾아보고 질문도 올려보고 검색도 해봤는데 그냥 배열의 크기를 잘못 설정해서 그런거였다ㅋㅋ 문제에서 순열의 크기는 최소 2, 최대 1000 이라고 했는데 이걸 착각하고 배열의 크기는 1000-2+1해서 999면 충분하다고 생각했다. 왜 그랬지? 아무튼 그래프 정점의 시작 노드는 1번..

[1260] DFS와 BFS(C++)

문제 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. www.acmicpc.net 내 코드(C++) #include #include #include #include #define MAX 1001 using namespace std; bool visit[MAX]; vectorlist[MAX]; void dfs(int start); void bfs(int start); int main(void) { int N, M, V; cin ..

[1697] 숨바꼭질(C++)

문제 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net 해결 방법 살짝 까다로웠던 문제. 분명 트리로 푸는건 아닌 것 같은데 자꾸 트리만 생각나고 bfs로 어떻게 풀어야할지 감이 안잡혀서 결국 구글링을 했다. 알고리즘은 간단하다. 1. 수빈이의 위치(n)..

[10026] 적록색약(C++)

문제 10026번: 적록색약 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 www.acmicpc.net 해결 방법 한 번에 맞은 문제가 진짜 오랜만인 것 같다 ㅋㅋ 좀 더 빨리 풀 수 있었는데 visited[i][j]가 초기화가 제대로 되지 않았던 탓에 시간을 좀 끌었다. 분명히 구글링한 결과로는 이..

[2583] 영역 구하기(C++)

문제 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다. www.acmicpc.net 해결 방법 저번주에 도전하다가 결국 실패해서 과제로 제출하지 못한 문제이다. 연휴라 시간도 많고 이걸 해결하지 못하면 다른 bfs문제도 풀 수 없을 것 같아서 다시 도전하기로 했다. 내가 생각하는 좌표의 시작점..

[2178] 미로 탐색(C++)

문제 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 해결 방법 DFS보다 BFS가 개인적으로 코드가 더 복잡하게 느껴져서 그런지 DFS로 풀 수 있는 문제는 무조건 DFS로 풀었더니 BFS로 푼 문제가 없어서 참고할 코드가 없었다... BFS 개념도 다시 찾아보고 결국 코드도 구글링 하긴 했다. 앞으로는 무조건 내 힘으로만 풀 수 있길.. 이 코드에서 가장 중요한 부분은 25, 54번째 줄인 것 같다. 미로를 int형으로 받는데 공백이 없이 들어오기 때문에 char형으로 선언하고 %s나 %c로 받는 방법도 있겠지만 %1d로 받음으로써 배열..