개발하는 개구리

🐸 문제 정보 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러 www.acmicpc.net 🤖 알고리즘 BFS ⏱️ 풀이 시간 30.20m 📝 풀이 그냥 BFS로 절대 통과 못할 줄 알았는데... 시간이 간당간당하게 맞은 것 같다. 구현이랑 섞인 BFS의 대표적인 문제 같은 느낌이었다. 나의 경우, 바이러스를 올릴 수 있는 노드와, 벽의 노드를 입력 때 미리 저장해두고 바이러스를 올릴 수 있는 노드에서 m개 만큼의 조합으로 BFS를 돌린 후, 벽의 노드를 제외한 노드가 모두 방문처리 되었는지 확인했다. 코드가 꽤 복잡하게 짜여진 것 같..다.. ..

🐸 문제 정보 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 🤖 알고리즘 BFS ⏱️ 풀이 시간 11.48m 📝 풀이 문제 내용이 너무 웃겼닼ㅋㅋㅋ 심지어 문제 자체도 괜찮아서 즐겁게 풀 수 있었다. 0, 0 부터 시작하면서 사방으로 이동하는 BFS 함수를 만든다 해당 함수의 경우, 이전에 방문 여부 대신 비용을 비교한다. 해당 지점까지 필요한 비용이 더 적은 경우에만 방문한다. 때문에 가격을 비교하는 배열의 초기값은 sys.maxsize로 설정했다. 🧑‍💻 나의 답 # pypy3 impo..

🐸 문제 정보 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 🤖 알고리즘 BFS ⏱️ 풀이 시간 36.01m 📝 풀이 문제가 엄청 복잡해보여서... 무조건 시간초과 or 메모리초과 날거라고 생각했는데 다행히 그렇게 복잡한 문제는 아니었다. 영역 구분할 때 초기 값에 uni를 넣어주는 것을 깜빡해서 1트는 실패했다ㅠ 입력값을 BFS 돌면서 영역 구분 구분된 영역을 돌면서, 사방에 바다가 있는 경우 bfs 시작 dist 리스트를 통해, 다른 영역까지의 거리를 1씩 더해줌 만약 돌다가 다른 영역 만나면 현재 저장된 거..

🐸 문제 정보 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 🤖 알고리즘 BFS ⏱️ 풀이 시간 38.02m 📝 풀이 BFS임에도 이렇게 오래 걸린 이유는.. 처음에 백트래킹으로 풀었고 + 순서에 따라 답이 달라지는거에 대해 고려하지 못했다. 생각해보면 단순한 BFS문제 같지만, 거리를 계산할 때 순서가 아래와 같아야한다. *2 시간이 늘어나지 않기 때문에 우선순위가 가장 높음 -1 +1 1번은 그렇다 쳐도, 2번 3번에 대한 해답은 질문 게시판을 뒤지다가 알아냈다! 글 ..

🐸 문제 정보 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 🤖 알고리즘 BFS ⏱️ 풀이 시간 10.06m 📝 풀이 BFS의 정석 같은 문제였다. 딱히 구현이 추가되거나 복잡하게 꼬여있는 것 없이, BFS 이론만 적용해서 풀 수 있는 문제였다. 도달하지 못하는 곳에는 -1을 넣어줘야하는게 복잡해 보일 수 있지만, 오히려 -1로 새로운 지도 배열을 선언해놓고 BFS 돌면서 값을 채워준다면 도달하지 못하는 곳에 자연스럽게 -1이 남게된다. 🧑‍💻 나의 답 # pypy..