BFS
-
BOJ) 뱀과 사다리 게임알고리즘/백준 2020. 6. 30. 14:48
뱀과 사다리 게임 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 풀이 이 문제는 BFS를 활용해 푸는 것이 효율적인 문제다. 딱히 어려운 점은 없었지만, 어이없이 두 번 실수한 부분이 있었다. 첫번째는 while을 통해서 입력받을 때다. for문을 두 번 쓰자니 번거로울 것 같아서 while로 한번에 받으려고 조건을 넣었었는데, 바보같이 or( || ) 조건이 아니라 and( && ) 조건을 걸었었다. 그리고, 처음 시작하는 좌표가 문제에서 1부터라고 제시돼 있었..
-
BOJ) 이모티콘알고리즘/백준 2020. 6. 29. 15:56
이모티콘 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만�� www.acmicpc.net 풀이 푸는데 시간이 조금 걸렸다. 처음에 풀었을 때는 n이 300정도 이상일 때, 시간이 너무 오래걸려서 가지치기를 계속 해줬다. 그래서 700정도까지는 통과할 수준으로 나올 수 있는데, 1000까지는 도저히 무리였다. 이 때는, visit을 이용하지 않았다. 굳이 필요 없었다고 생각했다. 하지만, visit변수를 만들어야겠다는 생각을 했고, screen에 표시된 스마일 갯수에 대해서만 visit을 체크해줬다. 그렇게 하니까 몇가지 경우에서 틀린 답이 ..
-
BOJ) 숨바꼭질알고리즘/백준 2020. 6. 26. 15:45
숨바꼭질 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 www.acmicpc.net 풀이 가장 빠른 step에서 위치를 찾아야하기 때문에, step에 따라 우선순위 큐를 이용해야한다고 생각했다. 그래서 class spot을 만들어서 Comaparable을 implement해서 사용했었는데, 63%에서 계속 틀렸다. 설마 step에 따라서가 아닌가 싶어서 Queue로 바꿔서 제출해봤는데 63%에서 틀렸다. 결론은, 로직 자제가 틀렸던 것이다. 더불어, 우선순위 큐가 필요가 없던 것이다. 우선순위를 체크안해도 된..
-
BOJ) 백조의 호수알고리즘/백준 2020. 6. 12. 23:29
백조의 호수 3197번: 백조의 호수 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있� www.acmicpc.net 풀이 처음 코테를 준비할 때 풀다가 실패한 문제였다. 그게 벌써 1년은 더 지난 것 같다. 1년간 매일같이 코테 연습을 하지는 않았지만, 실력이 많이 늘었을 거란 생각에 다시 도전했다. 하지만, 처참히 깨졌다... 처음으로 짰던 코드는, 가지치기 없이 BFS를 날마다 돌리면서 답을 찾는 것이었다. 6%에서 시간초과가 떴고, 시간 초과를 회피할 오랫동안 생각하다가 떠오르지 않아서 여러 블로그를 참고했다. Union-Find로 문제를 해결한 분들도 계셨..
-
알고리즘) 프로그래머스 Graph, 가장 먼 노드알고리즘/프로그래머스 고득점 Kit 2020. 4. 25. 15:50
프로그래머스 고득점 Kit - Graph 가장 먼 노드 풀이 2020.04.25) 그래프를 이용해 푸는 문제다. 이에 LinkedList와 PriorityQueue(우선순위 큐)를 이용해 BFS로 문제를 풀었다. 마지막 depth의 노드 수를 구하는 것이기 때문에 BFS가 적절하다고 생각됐다. 1. 루트인 1부터 시작해서 연결된 노드를 탐색한다. 2. 우선순위 큐에 depth를 기준으로 정렬해서 BFS 탐색을 할 수 있도록한다. 이때, visit을 남겨서 depth를 설정할 수 있게 도왔다. 3. depth별로 노드의 수를 세면서, depth가 깊어질 때마다 노드의 수를 0으로 초기화 시켜줬다. 4. 마지막 depth에서 while문을 탈출하면서 노드의 수를 센 result가 return될 수 있게 설정..
-
알고리즘) 프로그래머스 DFS/BFS, 여행경로알고리즘/프로그래머스 고득점 Kit 2020. 4. 21. 15:36
프로그래머스 고득점 Kit - DFS/BFS 여행경로 문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다. 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다. ..
-
알고리즘) 프로그래머스 DFS/BFS, 단어 변환알고리즘/프로그래머스 고득점 Kit 2020. 4. 21. 15:20
프로그래머스 고득점 Kit - DFS/BFS 단어 변환 문제 설명 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다. 두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 tar..
-
알고리즘) 프로그래머스 DFS/BFS, 네트워크알고리즘/프로그래머스 고득점 Kit 2020. 4. 21. 15:02
프로그래머스 고득점 Kit - DFS/BFS 네트워크 문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터..