DFS
-
[SWEA] 2819번 격자판의 숫자 이어 붙이기문제 풀이 2020. 4. 20. 17:23
2819 격자판의 숫자 이어 붙이기 풀이)dfs를 이용해서 서로 다른 일곱 자리 수들을 구한 문제이다.숫자의 자릿수가 늘어날 때마다 *10씩 하는 게 귀찮아서아예 string으로 선언해 stoi()함수로 수를 쉽게 구했다. 첫번째 풀이에서 일곱 자리 수들의 개수를 bool visited[1000000]을 통해 확인해주었고,이는 메모리를 너무 잡아먹었다. 코드) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include #include #include #include using namespace std; int arr[4][4];int check[10..
-
[백준] 17142번 연구소 3문제 풀이 2020. 4. 12. 16:52
17142 연구소 3 문제인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다.연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다.0은 빈 칸, 1은 벽, 2는 바이러스의 위치이다.연구소의 상태가 주..
-
[백준] 3109번 빵집문제 풀이 2020. 4. 6. 16:07
3109 빵집 문제빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열은 원웅이의 빵집이다.원웅이는 가스관과 빵집을 연결하는 파이프를 설치하려고 한다. 빵집과 가스관 사이에는 건물이 있을 수도 있다. 건물이 있는 경우에는 파이프를 놓을 수 없다.가스관과 빵집을 연결하는 모든 파이프라인은 첫째 열에서 시작해야 하고, 마지막 열에서 끝나야 한다. 각 칸은 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할 수 있고, 각 칸의 중심끼리 연결하는 것이다.원웅이는 가스를 되도록 많이 훔치려고 한다. 따라서, 가스관과 빵집을 연결하는 파이프라인을 여러 개 설치할 것이다. 이 경로는 겹칠 수 없고, 서로 접할 수도 없다. 즉, 각 칸을 지나는 파이프는 하나이어야 한다..
-
[백준] 9205번 맥주 마시면서 걸어가기문제 풀이 2020. 4. 5. 20:40
9205 맥주 마시면서 걸어가기 문제송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다.집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다.편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에..
-
[백준] 1520번 내리막길문제 풀이 2020. 4. 5. 17:57
1520 내리막길 문제여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이..
-
[백준] 3184번 양문제 풀이 2020. 3. 28. 14:21
3184 양 문제미키의 뒷마당에는 특정 수의 양이 있다. 그가 푹 잠든 사이에 배고픈 늑대는 마당에 들어와 양을 공격했다.마당은 행과 열로 이루어진 직사각형 모양이다. 글자 '.' (점)은 빈 필드를 의미하며, 글자 '#'는 울타리를, 'o'는 양, 'v'는 늑대를 의미한다.한 칸에서 수평, 수직만으로 이동하며 울타리를 지나지 않고 다른 칸으로 이동할 수 있다면, 두 칸은 같은 영역 안에 속해 있다고 한다. 마당에서 "탈출"할 수 있는 칸은 어떤 영역에도 속하지 않는다고 간주한다.다행히 우리의 양은 늑대에게 싸움을 걸 수 있고 영역 안의 양의 수가 늑대의 수보다 많다면 이기게 된다. 그렇지 않다면 늑대가 그 지역 안의 모든 양을 먹는다.맨 처음 모든 양과 늑대는 마당 안 영역에 존재한다.아침이 도달했을 ..
-
[백준] 16929번 two dots문제 풀이 2020. 3. 20. 19:23
16929 Two Dots 문제 Two dots는 Playdots, Inc.에서 만든 게임이다. 게임의 기초 단계는 크기가 N×M인 게임판 위에서 진행된다.각각의 칸은 색이 칠해진 공이 하나씩 있다. 이 게임의 핵심은 같은 색으로 이루어진 사이클을 찾는 것이다.다음은 위의 게임판에서 만들 수 있는 사이클의 예시이다. 점 k개 d1, d2, ..., dk로 이루어진 사이클의 정의는 아래와 같다.모든 k개의 점은 서로 다르다. k는 4보다 크거나 같다.모든 점의 색은 같다.모든 1 ≤ i ≤ k-1에 대해서, di와 di+1은 인접하다. 또, dk와 d1도 인접해야 한다. 두 점이 인접하다는 것은 각각의 점이 들어있는 칸이 변을 공유한다는 의미이다.게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구..
-
DFS & BFS알고리즘 2020. 3. 16. 16:50
들어가기 전, 그래프의 탐색이란? 어떤 정점에서 출발하여 그래프의 모든 정점을 방문하는 것 깊이를 우선으로 하는 깊이 우선 탐색과 너비를 우선으로 하는 너비 우선 탐색이 있다. 1. DFS (Depth First Search) 깊이 우선 탐색 개념? 현재 정점에서 이동할 수 있는 점들까지 들어가면서 탐색하는 방법 모든 정점(혹은 노드라고도 부름)를 방문하고자 하는 경우에 사용 다른 정점으로 이동할 수 없을때, 이전 정점으로 돌아가야하므로 거쳐온 정점들을 모두 저장해 주어야 한다. 구현 방법? 스택 또는 재귀함수로 구현, 즉 후입선출(LIFO) 원칙으로 탐색 어떤 정점을 방문했는지의 여부를 반드시 검사해야한다. *검사안할 경우 무한루프에 빠질 수 있다.* (ex) 2. BFS (Breadth Frist S..