프로그래민👨‍💻

단순한 DFS문제였다. 맨처음 백트래킹으로 접근하려했으나, 오른쪽과 아래로만 접근이 가능하기에 DFS를 적용하여 풀어주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 package algostudy3; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; publi..

Trie와 DFS를 활용한 문제였다. Trie를 활용하기 위해 Node라는 클래스를 만들고, 그안에 child라는 Map구조의 Node를 주었다. 일반 적인 Trie문제와 다르게 배열대신 Map을 활용해보았다. 그렇게 모든 입력들을 root아래 저장 후, DFS를 활용하여 출력을 해주었다. 단, 이때 알파벳순 출력이 필요하기때문에 Map의 keySet을 정렬된 리스트의 형태로 만들고 문제를 풀었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61..

DFS를 이용하는 문제였다. 맨처음 문제를 접했을때 아무생각없이 바로 DFS를 적용해봤는데, 역시나 최악의 경우 8^1000(전날의 떡을제외한 경우^날짜수)이 나오기때문에 시간초과를 면할 수 없었다. 그래서 바로 방문체크로 가지치는 방법을 택해주었다. visit[i번째날][떡]을 하나 만들어서 만일 이전날의 떡과 다르면서 visit[오늘][떡]이 방문 가능하다면 방문을 하고 방문체크를 해주는 방식으로 구현해보았다. 이렇게 된다면 어떠한 방식으로든 오늘에서 가질수 있는 떡을 중복으로 방문하는 것을 막을 수 있게 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 3..

DFS를 이용하여 트리의 구조에서 지름을 찾는 문제였다. 트리의 지름은 리프노드에서 리프노드까지의 거리를 의미하기 때문에 브루트포스의 형식으로 모든 노드를 탐색하면서 리프노드라고 판별될 경우 그 노드를 기준으로 DFS를 돌아서 다른 리프노드까지의 거리를 찾아서 비교하여 최대값을 구하는 방식으로 풀이해보았다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 package algostudy2..

위상정렬 혹은 DFS를 사용할 수 있는 문제였다. 이 문제는 트리 문제로써 각 위치마다 양 또는 늑대가 존재하고, 루트까지의 양의 총합을 구하는 문제였다. 트리를 형성하고, 전체를 순회하는 구조이기에 맨처음 DFS로 접근해보았다. 1번(루트)에서 DFS를 한번도는 방식을 구상하였는데, 양의 수를 구하기 위해 DFS를 돌때 리턴값(양의 수)을 가지게 되고 최종적으로 자식노드 부터 리턴값을 보내어 1번(루트)에서 받아보는 방식을 생각해보았다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 ..

플로이드와샬과 DFS를 같이 활용하는 문제이다. 내용자체를 이해하는데 좀 어려웠던 문제였다. 이 문제에서 결론적으로 구하는 것은 1. 서로 연결되어 있는 노드 중에서 2. 다른 노드로의 최대거리가 가장 작은 노드를 대표로 선정 하는 문제이다. 이러한 과정에서 1번을 해결하는 데에 DFS, 2번을 해결하는데 N값이 100이하이기에 플로이드와샬을 사용하였다. 전체적인 로직을 정리하자면 다음과 같다. N이 100이하이기에 플로이드와샬을 이용하여 전체 노드의 최단 경로를 map[][] 에 저장 1~N까지의 노드를 각각 확인하여 다른 노드로의 최대값을 maxDistanceToOther에 저장 그 후 1~N까지의 노드중 방문안한 노드에 대해 graph를 이용하여 DFS DFS를 돌면서 maxDistanceToOth..

dp와 dfs를 같이 활용한 문제이다. 저번에 풀었던 1520번 내리막길과 비슷한 문제이다. 마찬가지로 dfs를 도는데 최대 n의 크기가 500이 되므로 중간에 이차원 dp 배열을 통해 메모이제이션을 활용하는 전략을 사용했다. 이 문제도 마찬가지로 dp 이차원 배열을 -1로 초기화 시키고 dfs 의 반환값을 dp[i][j]로 반환하면서 dp값을 찾는 방식이다. 다만 이 문제에서 유의할점은 각 위치에서의 최대값을 찾는 것이기 때문에 dp를 갱신할때 dfs+1 (현재포함)한 값과 비교하여 최대값을 찾는 방식으로 구현해야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 ..

dfs와 dp를 같이 활용하는 문제였다. 맨처음 문제를 보았을때 백트래킹으로 접근해보았다. 하지만 M과 N이 최대 500을 가지고 있기에 시간초과를 우려하게 되었다. 따라서 메모제이션을 활용할 수 있는 dp를 같이 접목해보았다. dp[i][j]라는 배열을 두고 i,j에서의 M,N을 도달하는 방법의 수를 가지도록 설계를 하였다. 즉 dfs를 돈 경험이 있는 i,j 위치를 탐색해야할때 다시 dfs를 도는 것이 아니라 dp[i][j] 값만을 반환하도록 메모이제이션을 활용해주었다. 이 때 주의할점은 이차원 dp 배열의 초기값을 -1로 하는 것이랑 dfs 메소드가 dp[i][j]를 반환하도록 설계하는 것이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 2..

2020 카카오 인턴 4번 문제였다. 맨처음 봤을땐 단순하게 백트래킹+가지치기로 접근하였다. 하지만 역시 N이 최대 25였기에 시간초과가 발생하였다. 그래서 다르게 접근을 해보았다. visit배열을 int로 정의하여서 각 지점마다 최소가 되는 값을 저장해주었고, 갱신이 가능할때만 그 지점으로 갈 수 있도록 DFS를 구현하여 풀었다. 일종의 DP 개념으로 접근하여 DFS를 해결하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64..

그래프의 사이클을 찾는 문제이다. DFS를 이용하여 그래프의 사이클을 찾아서 pq에 저장하였다. DFS를 이용하여 그래프의 cycle을 찾을때는 visit 배열 뿐만 아니라 finished 배열을 하나 더 사용해준다. finished를 이용하여 이미 완전히 탐색이 끝났는지를 확인해주었다. DFS를 도는중 만일 visit가 true이지만 finished가 false 인곳을 찾는다면 cycle을 찾은 조건을 만족한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58..