프로그래민👨‍💻

DFS를 사용하는 문제지만 시간초과를 잘생각해야하는 문제이다. 일반적인 DFS를 사용한다면 시간초과가 쉽게 날수 있는 문제이다. 따라서 시간초과를 줄이기 위해 여러번 같은 노드를 방문하는 것을 주의 해야한다. 예를 들면 예제1번의 경우 1->3->3 이 나오고, 2->1->3->3 이 나온다. 2에서 시작한 경우 불필요하게 중복 방문을 하게 된다. 따라서 이런것을 해결해주기 위해 visit배열과 별개로 finished 배열을 만들어 노드에서 사이클을 이미 뽑아낸적이 있는 지를 체크해주었다. 또한, 탐색의 끝에 있는 노드는 항상 사이클을 형성 해주는 노드중에 하나 이므로 그 노드를 시작으로 다시 사이클을 체크해주는 방식을 사용하였다. 상당히 어려운 문제였다. 다시 풀어볼 필요가 있는 것 같다. 1 2 3 ..

시뮬레이션 문제이다. 주사위는 10번을 굴리고, 말은 4개를 가지고 있으므로 전체 경우의 수는 4^10을 가지게 된다. 따라서 이 문제는 백트래킹을 통한 완전탐색을 할 수 있는 문제이다. 다만 주의할점은 윷놀이판을 2차원 배열의 형태로 바꿔주는 것과 각 교차점에서 분기를 해주는 것이 중요하다. 또한 교차점의 값이 두번 안들어가도록 체크해주는 것도 중요하다. 그리고 백트래킹을 하는 과정에서 현재 점을 되돌려 놓는 것과 방문체크를 되될려 놓는 것이 포인트이다. 문제에 주어진 그대로 구현만하면 되는 시뮬레이션 문제였다. 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..

DFS를 이용하여 풀수 있는 문제이다. 일단 문제에서 10번이하로 움직인다는 조건을 주었다. 조건을 가지고 생각해보았을때 현재 구슬을 굴릴수 있는 방향은 4방향이 있고 10번을 굴린다 생각하면 전체가지수는 4^10이 나오게 된다. 4^10은 1,048,576‬ 로써 충분히 완전탐색을 할수 있는 시간이 나온다. 하지만 좀더 최적화가 가능하기에 생각을 해보았다. 맨처음 구슬을 굴릴땐 4방향 다 굴릴수 있지만 그다음부턴 2방향으로만 굴릴수있다. 예를 들어 맨처음 위쪽으로 굴렸다 가정해보자면, 구슬은 벽을 맞닿을때까지 구르기 때문에 다음번엔 위쪽으로 굴리는 것은 무의미한 경우를 가지게 된다. 또한, 반대방향이 아래쪽으로 굴리는 경우는 다시 그 전 상태로 되돌아가기 때문에 그것 또한 무의마하게 된다. 그래서 결론..

인접리스트의 DFS로 풀수있었던 문제이다. 리프노드에서 리프노드까지 가는 가장 긴경우를 지름이라 할 수 있는데 그것을 찾는 문제였다. 맨처음엔 가장 긴 간선을 기준으로 찾아보는 방법을 시도했는데, 가장 긴 간선이 꼭 포함되라는 보장이 없으므로 틀린방법으로 접근하였었다. 도움을 받아 풀었는데 다음과 같은 방법으로 풀었다. 1.루트에서 가장 멀리있는 리프노드의 인덱스를 찾고, 2. 그 리프노드에서 가장 멀리떨어진 리프노드의 거리가 지름. 이와 같은 방법으로 해결하였고, 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 4..

조합과 그래프탐색을 하는 시뮬레이션 문제이다. 이 문제를 접근할때 단순하게 생각하여 접근하였다. 일단 모든 도시들의 연결관계를 그래프를 이용하여 나타내주었고, 그후 도시들을 조합으로 1개부터 N/2개를 만큼 선택을 하였다. 그 후 같은 팀이된 도시들끼리 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 ..

이 문제는 DP로 해결하였다. 맨 처음 문제를 봤을때 재귀적인 그래프의 탐색형태로 접근하려고 했다. 하지만 N의 크기가 재귀를 사용하기에 너무 큰 경우의 수를 가지기에 재귀말고 DP로 접근하게 되었다. 일단 모든 맵의 칸에서 3가지의 경우의수를 가지고 했다. 파이프가 각각 가로,세로,대각선으로 깔리게 되는 3가지로 두었다. 그리고 만일 i,j에서 가로로깔리게 되는 경우의 수를 생각해보면 i-1,j 에서의 가로와 대각선의 경우의 수를 가질수 있게 된다. 이러한 방식으로 다음과 같이 생각하게 되었다. 1) i,j에서 가로의 파이프를 가지는 경우 : (i-1,j에서 가로) + (i-1,j에서 대각선) 2) i,j에서 세로의 파이프를 가지는 경우 : (i,j-1에서 세로) + (i,j-1에서 대각선) 3) i,..

백트래킹을 이용하여 경로를 찾는 문제이다. 백트래킹 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 package online.practice; import java.io.BufferedReader; import java.io.InputStream..

DFS를 이용하여 푸는 문제이다. 유향 그래프이기때문에 하나의 정점을 기준으로 1.정방향 DFS, 2.역뱡항 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 73 74 75 76 77 78 79 80 package boj2; import java.io.B..

이 문제는 여지껏 배운 다양한 알고리즘을 거의다 사용해야 풀 수 있다. 다음과 같은 로직으로 구현하였다. 1. BFS 또는 DFS 를 이용하여 섬을 찾고, 1부터 차례대로 섬에 대해 인덱싱을 해주기 2. 섬의수C2 인 조합을 이용하여 두개의 섬을 고르고, 가장 자리에 대해서 DFS를 이용하여 직선경로 찾기 3. 찾은 직선 경로에 대해 그래프의 형태를 만들기 4. 만든 그래프에 대해 모든 정점을 포함하며 정점보다 하나 적은 간선을 선택하게 되는 MST를 만들기 4-1. UnionFind를 이용한 간선 기준 Kruskal알고리즘 사용 4-2. PriorityQueue를 이용한 정점 기준 Prim 알고리즘 사용 다양한 알고리즘을 한번에 적용 시켜야 했던 문제이고, 여러가지를 다시 복습할 수 있어던 기회여서 좋..

처음에 보고 아이디어를 떠올리기 상당히 어려웠던 문제이다. 이 문제에서 전체 경우의 수를 따져본다면 전체 6팀이 경기를 하기때문에 총 15경기가 열리고, 경기마다 승,무,패 의 경우가 있기에 전체 3^15가지의 경우가 생기게 된다. 그러므로 백트래킹을 사용하여 승무패를 계속 재귀적으로 호출하면서 전체경우의 수랑 현재 테이블이랑 같아지는지 확인하여 구할수 있다. 백트래킹 문제라 전혀 생각지 못한 문제였다. 문제를 깊이 생각할 필요가 있다고 느꼈다. 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..