알고리즘70 [BOJ] 2239. 스도쿠(Python) / DFS 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 우리가 아는 그 스도쿠 게임이 맞다. 하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하는 문제이다. 사용 알고리즘 : DFS 맵을 인풋 받으며 0의 위치를 리스트에 담는다.(zeros) dfs 재귀로 depth == len(zeros)가 되는 순간 완성한 맵을 형식에 맞게 출력한다. 기본적인 dfs함수 틀에서 빈 자리에 1부터 9까지 숫자 중 가능한 숫자를 확인한다. 행 체크 : rowCheck() 함수에서 해당 행에서 같은 숫자 있으면 .. 2021. 4. 6. [BOJ] 2151. 거울 설치(Python) / BFS 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net 하.. 이 문제는 일주일 동안 나를 괴롭혔기에 더욱 각별하다.. 정말 많이 고민 했는데 답 보기가 너무 자존심 상해서 끝까지 답을 안 보고 혼자 고민했다. 길을 걸을 때나 샤워할 때나 자기 전에나 계속 머릿 속으로 문제 푸는 그런 거.. 다들 경험 있으리라 생각한다. 이틀에 한 번 정도 풀어서 제출하고 틀리고를 반복하다 오늘 뭔가 다시 풀어보자! 해서 풀었는데 역시나 제출하자마자 "틀렸습니다"를 받았다. 질문 게시판에 있는 반례를 모두 넣어보며 내 .. 2021. 4. 5. [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. 이전 1 2 3 4 5 6 7 8 ··· 12 다음
