Algorithm77 [BOJ] 2529. 부등호(Python) / DFS www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제 www.acmicpc.net 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾는 문제 사용 알고리즘 : DFS 재귀로 순열 구현하기 간단한 DFS 문제로 순열을 구하고 들어오는 각 숫자가 부등호에 부합하는 경우에만 재귀로 수를 더하며 넘기고, 부등호에 맞지 않다면 그냥 넘어간다.(isSatisfy 함수에서 확인) 가능한 경우일 때마다 최솟값, 최댓값을 갱신한다. 출력 시, 최댓값은 그대로 출력, 최솟값은 맨 앞 자리.. 2021. 4. 5. [BOJ] 16197. 두 동전(Python) / BFS 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 두 동전 중 하나만 보드에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성. 어렵지 않은 BFS 문제였다. # 1시간 17분 소요 사용 알고리즘 : BFS 최단 시간 알고리즘 input 받으며 두 동전의 위치 좌표를 받는다.(ar, ac, br, bc) bfs 함수에서 두 동전 좌표를 인자로 받는다. 함수 시작하며 check 라는 두 동전의 위치를 확인하기 위한 4차원 배열을 만든다. 그리고 두 동전의 첫 위치를 0으로 표시하고 큐에 담.. 2021. 4. 4. [BOJ] 4485. 녹색 옷 입은 애가 젤다지?(Python) / BFS 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 골드 4 문제인데 체감은 실버 1정도 되는 어렵지 않은 문제였다. N * N 맵의 (0, 0)위치에서 (N-1, N-1) 위치까지 가는데, 맵에 있는 값들을 더하며 이동한다면 목적지까지 도달하는 최솟값을 구하라. 문제 보자마자 BFS를 떠올렸고, 디버깅 없이 한 번에 코드를 짜서 pass를 받았다. # 30분 소요 사용 알고리즘 : BFS 너비 우선 탐색 일반적인 BFS 함수로, visited를 만들어 해당 위치까지 갈 수 있는 최솟값을 표시하.. 2021. 4. 3. [BOJ] 16954. 움직이는 미로 탈출(Python) / BFS 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 8X8 크기의 맵 왼쪽 하단에서 시작해 오른쪽 상단으로 탈출할 수 있는지 여부를 0과 1로 리턴하는 문제. 이 때, 욱제가 이동 후 맵 내의 벽이 한 칸씩 내려온다. # 1시간 31분 소요 사용 알고리즘 : BFS 너비 우선 탐색 우선, 내가 코드를 다 짜고 90%에서 계속 틀려서 반례를 살폈는데, 욱제는 이동하지 않고 제자리에 있을 수도 있다는 것이다. 즉, 8방향 + 제자리까지 해서 총 9개의 방향 델타 좌표를 탐색해야한다는 것! 벽이 움직이는 것은.. 2021. 4. 3. [BOJ] 16509. 장군(Python) / BFS 16509번: 장군 오랜만에 휴가를 나온 호근이는 문득 동아리방에 있는 장기가 하고 싶어졌다. 하지만 장기를 오랫동안 하지 않은 탓인지 예전에는 잘 쓰던 상을 제대로 쓰는 것이 너무 힘들었다. 호근이를 위해 www.acmicpc.net 10×9 크기의 장기판 위에 상과 왕의 처음 위치가 주어졌을 때, 상이 왕에게 도달할 수 있는 최소 이동 횟수 구하기 단, 이동 중 기물 있다면 해당 방향으로 이동하지 못한다. # 55분 소요 사용 알고리즘 : BFS 최단 거리 구하기 문제 그리기 전에 상이 갈 수 있는 8방향 델타 좌표(dr, dc), 위치별 장애물 좌표(obstacle)를 만들어뒀다. bfs에서 상의 첫 위치를 0으로 표현하고 큐에 담는다. 큐에서 꺼낸 위치에서 8방향 중 갈 수 있는 곳을 모두 boa.. 2021. 4. 2. [BOJ] 12851. 숨바꼭질 2(Python) / BFS 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 해당 번호까지 갈 수 있는 최소 시간과 그 시간에 갈 수 있는 방법은 몇 가지인지 추가적으로 구하는 문제이다! 예전에 숨바꼭질 1 풀었던 문제와 비슷하게 접근했는데, 추가로 구해야 하는 가짓 수 때문에 좀더 머리를 썼다. 사용 알고리즘 : BFS 최단 경로 알고리즘 먼저, K가 N보다 작거나 같다면 -1로 계속 가는 방법 뿐이다. 그러므로 N-K와 1가지 방법을 출력한다. 그렇지 않다면 bfs 함수를 실행해 최소 시간과 경우의.. 2021. 4. 1. 이전 1 2 3 4 5 6 7 8 ··· 13 다음
