본문 바로가기

Algorithm77

[BOJ] 17135. 캐슬 디펜스(Python) / DFS + BFS 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net # 1h 58m 소요 사용 알고리즘 : DFS + BFS / 자료구조 : 큐, 최소 힙(우선순위 큐) 오랜만에 이렇게 온갖 알고리즘이 섞인 문제를 풀었다. 장장 2시간여의 긴 여정이었다. 두 번째 푸는 문제라 나름 자신했지만, 처음에 코드 설계하고 다 풀고 디버깅하느라 시간이 좀 걸려서 아쉬웠다.. 한 번에 고려했어야 하는데! 일단 아래 코드는 죽일 적을 최소 힙 큐에 담으면서 가장 높은 우선순위의 적을 뽑아 사용하도록 했다. 시간, 메모리 면에서 매우 오래걸리는 코드라 또.. 2021. 4. 8.
[BOJ] 12904. A와 B(Python) / Greedy 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램 작성하는 문제 사용 알고리즘 : Greedy(탐욕 알고리즘) 처음에 백트래킹 완전탐색으로 구현했는데 제출하자마자 시간초과 났다. 알고리즘 구분을 보니 Greedy 알고리즘이더라. 다른 사람의 풀이를 보고 무릎을 탁! 쳤다. 생각을 바꿔서 T에서 S로 만드는 것이다. 조건을 반대로 생각해 T의 마지막 문자가 "A"이면 pop, "B"이면 pop 하고 문자.. 2021. 4. 8.
[BOJ] 6593. 상범 빌딩(Python) / BFS 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 빌딩의 상태를 3차원 배열로 받아 시작 위치부터 도착 위치까지 최단 거리로 갈 수 있는 경우의 거리를 구함 # 1시간 15분 소요 사용 알고리즘 : BFS 최단 거리 구하기 나의 비루한 코딩실력으로 인해 Input 받는 데만 28분이 걸렸다.. 별것도 아닌 것을.. 혼자 이상하게 생각ㅠ 이후로는 주어진 맵대로 3차원 배열인 것만 다르고 일반적인 BFS 문제와 같이 풀면 된다. Input 받으며 시작 좌표를 저장한다.(sl, sr, sc - 몇 층, 몇 행, 몇 열 순.. 2021. 4. 7.
[BOJ] 16929. Two Dots(Python) / DFS 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구하는 문제다. # 23분 소요 사용 알고리즘 : DFS 깊이 우선 탐색 설명할 것이 없는 듯.. 아래 코드와 같이 모든 정점에서 dfs를 돌리며 재귀로 갈 수 있는 곳으로 나아간다. 격자 밖이거나 이동할 곳의 문자가 다르다면 continue 방문할 수 있는 곳에만 방문 표시하며 재귀로 나아가고 출발지에 다다르고, 이동 횟수가 4번 이상이면 "Yes"를 출력하고 종료한다. 모든 재귀가 끝나도 사이클.. 2021. 4. 6.
[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.

티스토리툴바