💻

문제 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2

다익스트라 if(dist[to] > dist[from] + cost){ dist[to] = dist[from] + cost; } - D[i] = 시작 -> i 로 가는 최단 거리 - C[i] = i가 체크되어 있으면 true, 아니면 false 1. 체크되어 있지 않는 정점 중에서 D의 값이 가장 작은 정점 x를 선택한다. 2. x를 체크한다. 3. x와 연결된 모든 정점을 검사한다. 간선을 (x,y,z)라고 했을 때 d[y] > d[x] + z 이면 갱신해준다. 1, 2, 3단계를 모든 정점을 체크할 때까지 계속한다. - 모든정점 선택하므로(V-1) X 선택을 하는 데 걸리는 시간 O(V) = O(V^2) 인접행렬을 이용한 구현 for(int i=1; i

문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M*N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8*8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8*8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8..

문제 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다. 출력 총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다. 예제 입력1 3 0 1 0 0 0 1 1 0 0 예제 출력1 1 1 1 1 1 1 1 1 1 예제 입력..

문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다. ..

이전글 ) 2020/02/29 - [알고리즘/기본기 다지기] - [알고리즘][DFS와BFS 완전정복] 그래프의 표현 [알고리즘][DFS와BFS 완전정복] 그래프의 표현 어느정도 알고리즘 문제 풀이를 해 본 사람이라면 알겠지만 모든 코딩테스트에 거의 단골로 출제되는 문제가 바로 DFS, BFS 이다. 백준 문제풀이를 하면서 가장 나를 힘들게 했던 것도 바로 DFS와BFS!! 그래서 나.. hyonee.tistory.com 2. 그래프 탐색 DFS:깊이 우선 탐색 -> 최대한 깊숙히 많이 BFS:너비 우선 탐색 -> 최대한 넓게 가는 것 모든가중치가 1인경우 최단거리 탐색 - 위의 2가지 탐색 모두 목적은 모든 정점을 1번씩 방문하는 것 DFS - 스택을 이용해서 갈 수 있을 만큼 최대한 많이 가고 갈 수 ..

어느정도 알고리즘 문제 풀이를 해 본 사람이라면 알겠지만 모든 코딩테스트에 거의 단골로 출제되는 문제가 바로 DFS, BFS 이다. 백준 문제풀이를 하면서 가장 나를 힘들게 했던 것도 바로 DFS와BFS!! 그래서 나와 같이 알고리즘 문제풀이 새내기 왕초보들을 위해 완전 정복이라는 카테고리로 올리고자 한다. 글을 쓰면서 나도 공부하고, 자료가 부디 도움이 되길 바라는 마음입니다 :) 1. 그래프 표현 인접 행렬 - 양방향 그래프 일 때 A[i][j], A[j][i] - 인접 행렬은 없는 간선도 저장하기 때문에 자주 쓰이지는 않는다. 쉬운 문제를 풀 때 주로 사용한다. - 인접 행렬의 공간 복잡도는 O(V^2)이다. 가중치가 없는 경우) #include #include int a[10][10]; int m..

문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 예를 들어, 그림이 아래와 같은 경우에 ----------------------------------- RRRBB GGBBB BBBRR BBRRR RRRRR ----------------------------------- 적록색약이 아닌 ..