Redddy's Devlog

🔈 문제 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다. 빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오. 📝입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다. 각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주..

🔈 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 📝입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 📑출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 ..

🔈 문제 인제대학교 생화학연구실에 재직중인 석교수는 전류가 침투(percolate) 할 수 있는 섬유 물질을 개발하고 있다. 이 섬유 물질은 2차원 M × N 격자로 표현될 수 있다. 편의상 2차원 격자의 위쪽을 바깥쪽(outer side), 아래쪽을 안쪽(inner side)라고 생각하기로 한다. 또한 각 격자는 검은색 아니면 흰색인데, 검은색은 전류를 차단하는 물질임을 뜻하고 흰색은 전류가 통할 수 있는 물질임을 뜻한다. 전류는 섬유 물질의 가장 바깥쪽 흰색 격자들에 공급되고, 이후에는 상하좌우로 인접한 흰색 격자들로 전달될 수 있다. 김 교수가 개발한 섬유 물질을 나타내는 정보가 2차원 격자 형태로 주어질 때, 바깥쪽에서 흘려 준 전류가 안쪽까지 침투될 수 있는지 아닌지를 판단하는 프로그램을 작성하..

🧩문제 해석 수빈이와 동생은 일직선 상에 위치하고 수빈이는 1초에 x-1, x+1, 2*x 로 이동할 수 있다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하면 된다. 📚풀이 BFS를 사용하여 풀었다. 방문을 체크하기 위한 visited 리스트를 생성하였다. 큐에 현재 위치와 현재 누적 초를 같이 저장하여, 이동 할 때마다 초를 누적 시켜주었다. 이동 가능 위치는 arr 리스트로 만들어주었고, arr 요소 중 아직 방문 하지 않았고, 0~100000 사이 값이라면 방문하고 큐에 삽입 하였다. 그렇게 하여 k와 같은 값을 찾으면 현재 누적 초를 출력하였다. 만약 시작부터 동생과 수빈이가 같이 있다면 이동할 필요 없기에 0을 출력..

🧩문제 해석 F = 스타트링크 건물 층의 총 계수 S = 현재 강호의 위치 G = 스타트링크의 위치 U = 위로 올라가는 엘레베이터 층의 간격 D = 아래로 내려가는 엘레베이터 층의 간격 위 사항들이 주어졌을 때, 현재 강호의 위치에서 스타트링크의 위치로 엘레베이터로 가려 할 때, 누른 버튼의 최소값을 출력하는 문제이다. 만약 도달할 수 없다면, 계단 이용하라는 문장을 출력한다. 모든 층을 돌아다닐 필요가 없고 목표층에 도달하면 엘레베이터를 멈추면 되니까 BFS가 효율적이다. 📕 풀이 BFS로 풀었다. 이동할 수 있는 층은 [현재 위치 + U, 현재 위치 -D] 를 통해 유추하였고, 이 데이터가 F 안에 있고, 방문한 적이 없다면, 그 층으로 방문하였다. 💻 코드 from collections impor..

🧩문제 해석 체스 판의 크기와 현재 나이트의 위치 그리고 목표 위치가 주어졌을 때 최소 이동 횟수를 출력하는 프로그램! 📕 풀이 나이트의 이동 가능 경로는 다음과 아래의 그림과 같다. 최소 이동 횟수를 구하려면 이전에 방문 했던 곳은 지양한다. 그리고 체스판에서 벗어나는 위치도 제외한다. 이 두가지를 지키면서 BFS 탐색을 하였다. 칸을 모두 방문하는 것이 아니라 목표 위치에 도달하면 탐색을 멈출 것이기에 DFS 보다 BFS가 더 효율적이다. 💻 코드 import sys from collections import deque input = sys.stdin.readline # 나이트 이동 경로 dx = [-2,-1,1,2,2,1,-1,-2] dy = [1,2,2,1,-1,-2,-2,-1] def bfs()..

🧩문제 해석 이제 이런 문제들을 딱 보면 그래프 관련 문제라는 걸 바로 알아차릴 수 있게 되었다. '빙산 한 덩이가 주어졌을 때'가 조건에 들어가있으니, 무조건 빙산은 주어진다. 그러면 이제 빙산에서 얼음의 위치와 그 얼음 주위 환경을 살피면 된다. 그리고 빙산이 쪼개졌는지 BFS를 통해 확인한다. 🔉 풀이 전 잡담 앞서 말한 문제 해석을 알고리즘으로 구현해내는데에는 성공했다. 첫번째 제출에는 런타임 에러(RecursionError)가 발생했다. 이는 재귀함수가 너무 깊이 들어갈 경우 발생한다. 이땐 당황하지 말고 sys 모듈을 불러와 sys.setrecursionlimit(n) 을 적어주면 된다. 여기서 n은 최대 깊이를 의미한다. sys.setrecursionlimit(10**4) 을 넣어줌으로써 런..

※ 그래프 사진은 직접 그려서 추가예정! 갤럭시 탭이 오면 그걸로 그려야지ㅎ.ㅎ DFS와 BFS는 모두 그래프 탐색 알고리즘이다. 코딩테스트를 준비하다보면 어느 순간 만날 수 밖에 없는 알고리즘이다. DFS DFS는 Depth-first Search의 약자로 깊이 우선 탐색을 의미한다. 그래프의 가장 깊은 곳 우선으로 탐색을 하는 알고리즘이다. 스택 자료구조를 사용하여 그래프를 탐색한다. DFS의 탐색과정은 다음과 같다. 탐색 시작 노드를 스택에 넣고, 방문 처리한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면, 그중 가장 작은 값의 인접 노드를 스택에 넣고 방문처리한다. 만약 방문하지 않은 인접 노드가 없다면 스택의 최상단 노드를 꺼낸다. 2번의 과정을 더 이상 수행할 수 없을 때가지 반복..