dfs
-
[Baekjoon Online Judge] 10974번: 모든 순열문제 풀이/Baekjoon Online Judge 2021. 4. 21. 19:34
10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 요구사항 - N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. 입력 - 첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다. 출력 - 첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다. DFS를 활용하여 풀이하였다. 순열을 사전순으로 출력해야 하기 때문에 입력이 3인 경우 첫 자리는 1, 2, 3이 올 수 있다. DFS를 활용하여 depth를 높여가며 output을 하나씩 방문해준다. 만약 depth의 깊이가 3과 같아지면 3개의 항목을 채웠다고 가정하고 즉시 출력해준다. 그 다음 방문기록을 f..
-
[Baekjoon Online Judge] 2583번: 영역 구하기문제 풀이/Baekjoon Online Judge 2021. 2. 22. 15:39
2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 요구사항 - 눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. - M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그..
-
[Baekjoon Online Judge] 1987번: 알파벳문제 풀이/Baekjoon Online Judge 2021. 2. 21. 12:24
1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 요구사항 - 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. - 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. - 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있..
-
[Baekjoon Online Judge] 14501번: 퇴사문제 풀이/Baekjoon Online Judge 2021. 2. 13. 12:35
14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 요구사항 - 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. - 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. - 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표가 입력으로 주어졌다고 가정한다. 1일 2일 3일 4일 5일 6일 7일 Ti 3 5 1 1 2 4 2 Pi 10 20 10 20 15 40 200 - 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수..
-
[Baekjoon Online Judge] 14502번: 연구소문제 풀이/Baekjoon Online Judge 2021. 1. 19. 17:46
14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 요구사항 - 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. - 연구소는 크기가 N x M인 직사각형으로 나타낼 수 있다. - 연구소는 빈 칸, 벽으로 이루어져 있다. 벽은 칸 하나를 차지한다. - 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우 인접한 빈 칸으로 모두 퍼져나갈 수 있다. - 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다. - 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 입력 - 첫째 줄에 지도의 세로 크기 N..
-
[Baekjoon Online Judge] 1260번: DFS와 BFS문제 풀이/Baekjoon Online Judge 2021. 1. 12. 22:32
1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net [그래프 탐색] DFS와 BFS 1. 그래프란? 그래프는 vertex(정점)와 vertex(정점)를 이어주는 edge(간선)로 이루어져 있다. 정점은 대상이나 개체를 나타내고, 간선은 이들 간의 관계를 나타낸다. 상호 관계가 대칭적이지 않은 hyeonic.tistory.com 간선을 연결하는 두 정점의 번호를 입력 받아 그래프를 그리고 DFS와 BFS로 탐색한다. DFS와 BFS에 대한 설명은 https://hyeonic.t..
-
[그래프 탐색] DFS와 BFS문제 풀이/Baekjoon Online Judge 2021. 1. 12. 20:31
1. 그래프란? 그래프는 vertex(정점)와 vertex(정점)를 이어주는 edge(간선)로 이루어져 있다. 정점은 대상이나 개체를 나타내고, 간선은 이들 간의 관계를 나타낸다. 상호 관계가 대칭적이지 않은 경우 방향을 가진 간선으로 나타낼 수 있다. 이때 이러한 그래프를 방향을 가진 그래프 혹은 Direct Graph 유향 그래프라고 한다. 반면 간선의 방향이 없는 그래프를 무방향 그래프 혹은 Undirected Graph 무향 그래프라고 한다. 2. 그래프의 표현 그래프의 표현 방법에는 행렬을 이용하는 방식과 리스트를 이용하는 방식이 있다. 2.1 인접 행렬 그래프 G = (V, E)에서 정점의 총 수를 n이라고 가정하자. 행렬의 크기는 n x n 행렬이 된다. 정점 i와 정점 j 사이에 간선이 존..