본문 바로가기

분류 전체보기

 (120)
[BOJ] 16929. Two Dots(Python) / DFS 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구하는 문제다. # 23분 소요 사용 알고리즘 : DFS 깊이 우선 탐색 설명할 것이 없는 듯.. 아래 코드와 같이 모든 정점에서 dfs를 돌리며 재귀로 갈 수 있는 곳으로 나아간다. 격자 밖이거나 이동할 곳의 문자가 다르다면 continue 방문할 수 있는 곳에만 방문 표시하며 재귀로 나아가고 출발지에 다다르고, 이동 횟수가 4번 이상이면 "Yes"를 출력하고 종료한다. 모든 재귀가 끝나도 사이클..
[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() 함수에서 해당 행에서 같은 숫자 있으면 ..
[BOJ] 2151. 거울 설치(Python) / BFS 2151번: 거울 설치 첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 www.acmicpc.net 하.. 이 문제는 일주일 동안 나를 괴롭혔기에 더욱 각별하다.. 정말 많이 고민 했는데 답 보기가 너무 자존심 상해서 끝까지 답을 안 보고 혼자 고민했다. 길을 걸을 때나 샤워할 때나 자기 전에나 계속 머릿 속으로 문제 푸는 그런 거.. 다들 경험 있으리라 생각한다. 이틀에 한 번 정도 풀어서 제출하고 틀리고를 반복하다 오늘 뭔가 다시 풀어보자! 해서 풀었는데 역시나 제출하자마자 "틀렸습니다"를 받았다. 질문 게시판에 있는 반례를 모두 넣어보며 내 ..
[BOJ] 2529. 부등호(Python) / DFS www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제 www.acmicpc.net 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾는 문제 사용 알고리즘 : DFS 재귀로 순열 구현하기 간단한 DFS 문제로 순열을 구하고 들어오는 각 숫자가 부등호에 부합하는 경우에만 재귀로 수를 더하며 넘기고, 부등호에 맞지 않다면 그냥 넘어간다.(isSatisfy 함수에서 확인) 가능한 경우일 때마다 최솟값, 최댓값을 갱신한다. 출력 시, 최댓값은 그대로 출력, 최솟값은 맨 앞 자리..
[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으로 표시하고 큐에 담..
[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를 만들어 해당 위치까지 갈 수 있는 최솟값을 표시하..
[BOJ] 16954. 움직이는 미로 탈출(Python) / BFS 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 8X8 크기의 맵 왼쪽 하단에서 시작해 오른쪽 상단으로 탈출할 수 있는지 여부를 0과 1로 리턴하는 문제. 이 때, 욱제가 이동 후 맵 내의 벽이 한 칸씩 내려온다. # 1시간 31분 소요 사용 알고리즘 : BFS 너비 우선 탐색 우선, 내가 코드를 다 짜고 90%에서 계속 틀려서 반례를 살폈는데, 욱제는 이동하지 않고 제자리에 있을 수도 있다는 것이다. 즉, 8방향 + 제자리까지 해서 총 9개의 방향 델타 좌표를 탐색해야한다는 것! 벽이 움직이는 것은..
[BOJ] 16509. 장군(Python) / BFS 16509번: 장군 오랜만에 휴가를 나온 호근이는 문득 동아리방에 있는 장기가 하고 싶어졌다. 하지만 장기를 오랫동안 하지 않은 탓인지 예전에는 잘 쓰던 상을 제대로 쓰는 것이 너무 힘들었다. 호근이를 위해 www.acmicpc.net 10×9 크기의 장기판 위에 상과 왕의 처음 위치가 주어졌을 때, 상이 왕에게 도달할 수 있는 최소 이동 횟수 구하기 단, 이동 중 기물 있다면 해당 방향으로 이동하지 못한다. # 55분 소요 사용 알고리즘 : BFS 최단 거리 구하기 문제 그리기 전에 상이 갈 수 있는 8방향 델타 좌표(dr, dc), 위치별 장애물 좌표(obstacle)를 만들어뒀다. bfs에서 상의 첫 위치를 0으로 표현하고 큐에 담는다. 큐에서 꺼낸 위치에서 8방향 중 갈 수 있는 곳을 모두 boa..

티스토리툴바