DFS
-
[프로그래머스] 여행경로문제 풀이 2020. 5. 15. 17:06
문제 설명주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다.항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.제한사항모든 공항은 알파벳 대문자 3글자로 이루어집니다.주어진 공항 수는 3개 이상 10,000개 이하입니다.tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.주어진 항공권은 모두 사용해야 합니다.만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.입출력 예ticketsreturn[[ICN, JFK], [HND, IAD..
-
[SWEA] 5656 벽돌깨기문제 풀이 2020. 5. 14. 22:04
5656 벽돌깨기 풀이)모든 경우를 확인해보는 문제였다. 처음에 없애는 벽돌에 적힌 숫자만큼이나 상하좌우 다른 벽돌을 제거하는 걸 어떻게 처리할까 싶었는데그냥 벽돌에 적힌 수만큼 상하좌우 모두 방문 해보고 바꿔주면 되었다.-> 다 방문한다!! 간단히 풀이과정을 말해보자면 1. dfs을 통해 어떤 행의 벽돌을 없앨 건지, 행들의 순열(n개 길이)을 구한다.2. 그 순열 순서대로 벽돌을 없애고, 벽돌을 내리는 행위를 반복한다. -> 벽돌없애는 과정도 dfs를 통해 없앤다. 벽돌을 없애는 함수는 -> change()벽돌을 내리는 함수는 -> relocate() 주의할 점재귀 방법을 이용해서 벽돌을 없애므로, 이전 상태의 값을 저장해놓고되돌아 왔을 때 원래 값으로 다시 바꿔줘야한다는 점이다. 코드) 123456..
-
[SWEA] 4012 요리사문제 풀이 2020. 5. 13. 23:03
4012 요리사 풀이)문제 자체는 어렵지 않았다.dfs를 이용해 각 음식마다 어떤 식쟤료를 가질건지 결정한 다음, 시너지 계산하는 완전 탐색 문제였다. 그런데 처음에 시간초과 나길래 당황했다.알고보니, n개의 식재료가 있다면 음식 1을 위해 n/2 개까지만 고르고 나머지 쟤료들은 음식 2를 위해 쓰면되는데쓸데없이 식재료 n개의 나올 수 있는 모든 조합을 다 보고 있었다.즉, 음식 1을 위해 n/2개만 고르면 되는데 1~n개까지 고르는 경우를 다 확인한 것이다.(그리고 나서 n/2개씩일때만 계산하게 함) 다시 풀때는 n/2개만 고르고 나머지들은 자동적으로 다른 음식 2를 위해 쓰이게 풀어줬다. 코드) 12345678910111213141516171819202122232425262728293031323334..
-
[SWEZ] 2383 점심 식사시간문제 풀이 2020. 5. 11. 21:15
2383 점심 식사시간 풀이)정말 어이없게 시간이 걸린 문제이다.계단 내려가는 시간을 저장하는 배열(int s_time[2])을 테스트케이스마다 초기화 하지 않아서 틀린건데방법이 틀려서인줄 알고 계속 고민했다., 그냥 초기화를 안한거...초기화를 잘하자.. 풀이과정을 간략히 말하자면 이러하다.먼저 조합방식(dfs)을 이용해 각 사용자가 어떤 계단을 이용할지 정해줬다. 모든 사용자가 어떤 계단을 사용할지 결정되었다면, 직접 만든 cal()함수를 통해 시간을 계산해줬다. cal()함수의 구성은 이러하다vector time[2]; // 첫번째 계단과 두번째 계단을 이용하기로 한 사용자들이 각자 계단까지 걸리는 시간(이동시간) 저장한 것 time 벡터를 오름차순으로 정렬하면, 각자 계단마다 언제 사용자가 먼저 ..
-
[SWEA] 1952. 수영장문제 풀이 2020. 5. 8. 20:22
1952 수영장 풀이)DFS를 이용해서 모든 경우를 다 확인해보면 되는 문제였다. 1월에만 1년 이용권을 살 수 있고,그 외 나머지 월에는 1일, 1달, 3달 이용권을 살 수 있는 선택지가 있다.그 조합들을 다 확인해보면 된다. 코드) 12345678910111213141516171819202122232425262728293031323334353637383940414243#include #include using namespace std; int cost[4];//1일, 1달, 3달, 1년int result;int month[13]; void dfs(int wal,int res) { if (wal > 12) { result = min(result, res); return; } if (wal == 1) {..
-
[SWEA]2105 디저트 까페문제 풀이 2020. 5. 1. 21:42
2105 디저트 까페 풀이)dfs를 이용해서 푼 문제이다. 최대한 중복되는 사각형 모양을 거르기 위해 두가지 방법을 사용했다.1. 맨왼쪽, 맨오른쪽, 맨아래쪽에서 시작하는 경우는 사각형을 이루지 못하므로 계산에서 제외한다.2. 사각형으로 움직일때, 무조건 오른쪽 아래부터 시작한다. 주의할 점출발점으로 돌아왔을때, 디저트의 수는 무조건 4개 이상이며 방향으로 제일 마지막 방향 상태여야한다. 코드) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include #include using namespace std; int n;int map[21]..
-
[SWEA] 1949 등산로 조성문제 풀이 2020. 4. 29. 22:24
1949 등산로 조성 풀이)dfs를 이용해서 가능한 모든 경우를 다 살펴본 문제이다. 과정은 이러하다.1. 가장 지형이 높은 곳들의 위치를 저장해 둔다.2. 각 높은 곳들의 위치에서 dfs를 통해 등산로 길이를 구한다.3. 그 중 최고의 등산로 길이를 출력한다. dfs함수를 자세히 설명하면1) 현재 좌표값에서 상하좌우로 움직였을때 지도 범위내에 들어오는 지 확인2) 범위내에 들어온다면 이전에 지형을 깎아본 적이 있는 지 확인 2.1) 지형을 이미 깎아봤다면다음에 움직일 곳의 지형의 높이 확인현재 지형의 높이보다 작다면 → 이동작지 않다면 →이동 그만하고 지금까지의 등산로 길이 체크 2.2) 지형을 아직 깎아보지 않았다면다음에 움직일 곳의 지형의 높이를 확인현재 지형의 높이보다 작다면 → 이동작지 않다면 ..
-
[SWEA] 1824 혁진이의 프로그램 검증문제 풀이 2020. 4. 21. 22:48
1824 혁진이의 프로그램 검증 풀이)dfs를 통해 탐색해준 문제이다. 주의할점은 ? 문자와 cycle 여부이다. 1. ? 문자일 경우, 4방향으로 바뀔 확률이 동일하니깐 4방향 모두 탐색해봄으로 해결했다. 2. sample_input의 2번 처럼, (sample 2) 2 6 5>--v. .^--_@ 탐색이 끝나지 않고 계속 돌아가는 상황이 생길 수 있다. -> cycle 생성 이는 bool visited[20][20][16][4] 4차원 배열을 통해 한 번 겪었던 상황이면 다시 겪지 않도록 해줬다. visited[r][c][mem][direction] == true? : r행 c열 번째 칸을 메모리에 mem 정수가 저장되어있고, 방향이 dir일때 방문했었다 라는 뜻. 코드) 123456789101112..