프로그래민👨‍💻

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

조합과 BFS가 합쳐진 문제이다. 이 문제는 바둑판에서 0이 되는 곳의 위치 2개를 뽑는 조합을 사용한다음, 1로 둘러쌓인 2의 최대 갯수를 구하는 BFS문제이다. 이 문제에 주의할점은 2가 테두리 혹은 1로 만 둘러쌓여야 하는데 이과정에서 나는 flag변수 possible을 하나 선언하여 0이랑 인접해있으면 count를 할수 없게 처리하였다. 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 ..

구현할 것이 상당히 많은 문제였다. 기본적으로 벽이 갈수 있는 위치 3군대를 찾는 과정을 거치고 벽을 셋팅후 BFS하여 모든 0의 갯수를 세어주는 과정을 찾는 문제였다. 조합과 BFS를 연속하여 구현하기 때문에 빼먹을수 있는 부분이 많은 문제이므로 꼼꼼하게 함수로 나누어 코딩하는게 중요한 문제였다. 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..

BFS를 이용하여 구현하는 문제이다. 이 문제에서 유의할게 여러가지 있었다. 갱신을 하는 과정에서 생명력 수치가 높은 줄기 세포가 그리드 셀을 차지 하는 것, X시간 동안 비활성 상태를 거치고 X시간이 지나는 순간 X시간 동안 활성상태가 되는 것, 맵의 크기가 제대로 주어지지 않는 점등 구현에 까다로운 점이 많았다. 다음과 같이 해결하였다. 생명력 수치가 높은 세포로 갱신 -> PriorityQueue를 이용하여 생명력이 높은 세포들이 가장 위에 올수있도록 사용 X시간 후 X시간 동안 활성 -> curLive가 0이 되기전까지 계속 PrioirtyQueue에 남겨두기 맵의 크기 -> 주어진 r,c값에 time*2를 더해준 만큼 크기를 잡기 구현의 고려요소가 많아서 상당히 오랜시간을 풀었고, 많은 것을 참..

C에서 C까지의 최단경로를 찾는 BFS문제이다. 최단경로를 찾을때 다익스트라 알고리즘 또한 사용가능하지만, 이 문제에선 BFS를 사용하여 구현하였다. 이 문제는 자신의 방향과 방향전환횟수를 알고있어야해서 Pos라는 class에 담아둔 상태로 구현하였다. 맨처음엔 일반 visti[][] 배열을 사용하여 방문하지 않았으면 방문하고, 만일 방문했더라도 갱신이 가능하다면 다시 방문하는 방식을 사용하였다. 하지만 어느부분에서 처리가 잘되지않아 다른방법을 사용하였다. 벽을 부수고 이동하기 처럼 visit[][][] 3차원 배열을 사용하였다. 즉 visit[row][col][조건]으로 두고 풀었다. 이 문제에선 조건 부분이 방향을 뜻하는 4가지방법을 의미하여 이와같이 풀어 해결하였다. 1 2 3 4 5 6 7 8 9..

그래프를 사용하여 DFS와 BFS를 하는 기본 문제이다. 그래프를 인접리스트로 구현하여 DFS와 BFS각 각 구현하였다. DFS를 구현할 때는 stack을 사용하는 대신 재귀의 형태로 구현하였다. BFS를 구현할 때에는 queue를 사용하여 구현하였다. DFS에서는 방문할때 바로 visit 체크를 해주었고, BFS에서는 queue에 offer하는 동시에 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 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 ..

BFS를 활용하는 문제이다. 그러나 일반적인 BFS를 사용한다면 틀린 답을 출력할 것이다. 왜냐하면 클립보드라는 개념을 이문제에선 가지고 있는데 S개의 아이콘을 만드는데 걸리는 시간을 T라고 한다면, 같은 S개를 만들더라도 클립보드의 수에 따라 각 각 다른 T를 가지게 된다. 이 이유는 그래프에서 예를 찾을 수 있는데, 정점 A에서 B를 가고 싶을때, 간선1을 선택해서 가는 경우랑 간선2를 선택해서 가는경우가 있다 가정하자. 같은 B를 도달했더라도 다른 간선을 선택하여 왔기때문에 다른 경우의 수라 생각할 수 있다. 즉, 문제로 다시 돌아와본다면 클립보드의 수에 따라 같은 S개를 만들더라도 다른 T시간을 가질 수 있기 때문에 시간을 저장하는 배열 visit를 2차원의 배열의 형태로 작성하였다. 즉 visi..

이 문제는 BFS를 계속 반복하면서 문제에 주어진 조건대로 구현하는 시뮬레이션 문제이다. 문제를 다소 어렵게 생각했었지만, 꼼꼼히 읽어보니 있는 그대로 구현하면 되는 문제였다. 4개이상 똑같은 알파벳이 연결된 것이 있나 BFS를 이용하여 찾고, 폭파시킨다음 맵을 아래로 내리면서 계속 반복하는 문제이다. 맵을 끌어 내리는 함수는 mapDown() 이라는 함수를 이용하였는데, 맨 아래 행부터 시작해 '.'을 찾으면 위의 있는 문자와 바꾸어 주는 형식으로 구현하였다. 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..

여러가지 기법이 혼합되어 있는 문제이다. 우선 전체 25개의 알파벳중 7개를 뽑는 경우의 수를 생각하였다. 백트래킹을 이용한 조합을 사용할 계획으로 7개의 알파벳을 고르는 것을 구현한 후 1차적으로 S가 4개 이상인지를 확인하였다. 그 다음 S가 4개이상임이 확인이 된다면 BFS를 이용하여 7개의 알파벳이 하나의 그룹으로 이루어져있는지 확인하였다. 만일 하나의 그룹이면 최종답을 하나추가 시켰다. 수의 범위가 구현이 가능한 범위임으로 문제에 주어진 대로 구현하는게 중요한 문제였다. 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 4..

BFS를 활용하는 문제이다. 이 문제의 경우 불(*)의 경우와 사람(@)의 경우가 있으므로 visit배열을 2차원 두개를 이용하기위해 3차원으로 선언하여 각 각 구분하여 문제를 접근하였다. 또한, 불길이 사람보다 먼저 번지기 때문에 일반적인 queue보단 deque를 이용하여 불길이 deque앞쪽에 들어가 있게 했다. 위의 두가지 포인트가 기본적인 BFS 문제와 차이점을 보였던 문제이다. 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..