링크 : https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 문제 소요시간: 56분 7초 설계하기(접근방법) 1. 입력받기 입력받는것이 정말 까다로웠다. x의 배수에 주의하여 3차원 배열로 입력받는다 2. 구현하기 dx dy뿐만 아닌 dz까지 선언하여 bfs로 순회를 해준다 끝난 지점의 최단 시간을 저장한다 3. 출력하기 최단 시간이 존재한다면 포맷 형태로 출력하고 존재하지 않는다면 Trapped를 출력한다. 코드(출력) from collections ..
링크 : https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제 소요시간: 17분 1초 설계하기(접근방법) 1. 입력받기 건물 크기, 목표 층, 시작 층 위 버튼 아래 버튼을 입력받는다 2. 구현하기 dx = [up,down]으로 선언해서 bfs를 돈다 3. 출력하기 목표 층에 방문한 경우 최단경로 횟수를 방문하지 않았다면 use the stairs를 출력한다 코드(출력) from collections import deque building, start, e..
링크 : https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 문제 소요시간: 15분 6초 설계하기(접근방법) 1. 입력받기 행열 크기와 쓰레기 위치를 입력받는다 2. 구현하기 다른 문제들과 같다. 입력받는 행열을 탐색하고 bfs 한번을 수행할 때 몇번의 q.apppend()가 이루어지는지 카운트하면 그것이 넓이이다 3. 출력하기 가장 큰 넓이를 출력한다 코드(출력) from collections import..
링크 : https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 소요시간 : 22분, 예외케이스 디버깅 1시간 설계하기(접근방법) 1. 입력받기 숫자를 입력받는다 2. 구현하기 이중배열 혹은 리스트를 2개 선언해서 이전 경로를, 시간과 함께 담는다 그 후 end에 다다르면 경로를 역추척한다 역추적한 경로를 리스트에 담는다 3. 출력하기 역추적 경로 리스트를 뒤집어서 출력한다 코드(출력) from collectio..
링크 : https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제 소요시간: 42분 36초 설계하기(접근방법) 1. 입력받기 숫자를 입력받는다 2. 구현하기 다른 숨바꼭질 문제와 유사하다 핵심은 곱셈의 경우 가중치가 0이기 때문에 처리를 잘 해줘야 한다 곱셈을 먼저 처리하지 않으면 1 -> 2 로 증가시킬 때 시간이 +1이 되기 때문에 오답이 난다 3. 출력하기 최소 시간을 출력한다 코드(출력) from col..
링크 : https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제 소요시간: 45분(50%) 통과 설계하기(접근방법) 1. 입력받기 숫자를 입력받는다 2. 구현하기 이 문제의 어려웠던 점은 최소시간을 구하는 것이 아닌 최소 시간의 방법 수를 구하는 것이었다 즉 1 -> 4로 가는 경우 1+1 2 * 2 를 하거나 1 * 2 2* 2 두 가지 방법이 있는데 이 두 가지 경우를 어떻게 체크하냐 였다. que에 ap..
링크 : https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 소요시간: 18분 35초 설계하기(접근방법) 1. 입력받기 시작 지점과 목표 지점을 입력받는다 2. 구현하기 bfs 문제인데 배열을 만든다 nx = [-1, +1, i ==2 일 때 x *= 2] visited 배열을 100001개를 선언해주고 nx의 범위 역시 100000을 벗어나지 않도록 해준다 각각의 케이스를 q에 apppend 하고 nx가 targe..
링크 : https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제 소요시간: 47분5초 설계하기(접근방법) 1. 입력받기 행열을 입력받는다 2. 구현하기 graph를 이전 문제들은 입력받았었다면 이번에는 직사각형의 위치를 입력받아 직사각형의 위치를 제외해주고 bfs로 넓이를 탐지해주면 된다 그 후 직사각형의 넓이를 리스트에 append해준다 3. 출력하기 직사각형 배열의 길이와 넓이들을 정렬해서 출력해준다 코드(출력) from ..
