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 이런 유형의 문제를 처음 보면 '이게 왜 BFS문제지?' 라는 의문이 든다. S층에서 G층으로 가는데 U칸 위로가거나 D칸 아래로 가야하므로 1. 처음에 visited[S]를 방문 처리를 해주고 q에 S를 넣는다. 2. q에서 pop한 뒤 x + U에 해당하는 칸에 방문한 적 있는지 확인하고 없으면 버튼을 누른 횟수를 1 증가시킨다. 3. 2번과 마찬가지로 x - D에 해당하는 칸에 방문한 적 있는지 확인하고 없으면 버튼을..
www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 이제는 무난한(?) BFS문제이다. 단지 3차원배열을 사용해 조금 귀찮을 뿐이다. 1. Test Case마다 m(빌딩상태), time(이동시간), visited(방문여부) 배열을 초기화해주고 m을 입력받는다. 2. m을 전체돌면서 'S'가 있는 칸의 좌표를 sz, sx, sy에 저장하고, 'E'가 있는 칸의 좌표를 ez, ex, ey에 저장한다. 3. bfs를 돌리면서 다음 칸으로 갈때마다 시간을 1씩 더해주고 큐에..
www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net import sys from collections import deque input = sys.stdin.readline q = deque() M, N, H = map(int,input().split()) dx, dy, dz = [1,-1,0,0,0,0], [0,0,-1,1,0,0], [0,0,0,0,-1,1] m = [[list(map(int,input().split())) for _ ..
www.acmicpc.net/problem/21316 21316번: 스피카 위 그림은 처녀자리 중 12개의 별을 12개의 선분으로 이어 만든 그림이다. 시은이는 임의로 각 별에 1부터 12까지의 서로 다른 정수 번호를 부여하고, 12개의 정수 쌍으로 각 선분이 어떤 두 별을 www.acmicpc.net # 입력되는 숫자만 다르고 그래프 모양은 같으므로 "Spica가 몇번인지 어떻게 판단할까??" 생각해본 결과 그래프의 정점의 간선의 갯수로 판단을 해보자고 생각했다. 1. 별자리가 그래프라고 생각하고 x, y가 입력되면 서로 연결되있는 것으로 생각했다. dic[x]에 y를 append하는 식으로 x정점과 연결되어있는 정점들을 모두 저장했다. 별자리를 보면 알 수 있듯이 정점과 연결된 간선의 갯수는 모두 1..
www.acmicpc.net/problem/21318 G번: 피아노 체조 피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 www.acmicpc.net 단순히 수학문제여서 정석대로 풀었다가 혼쭐난 문제이다. 1. 처음에 그냥 for문으로 hard배열(난이도)를 돌면서 현재 난이도가 다음 난이도보다 높으면 miss에 1을 더해주고 miss를 return 해주는 식으로 풀었다. import sys input = sys.stdin.readline N = int(input()) hard = list(map(int,input().split())) def mistake(x,..
www.acmicpc.net/problem/18291 18291번: 비요뜨의 징검다리 건너기 강을 건너는 방법은, (1 → 4), (1 → 2 → 4), (1 → 3 → 4), (1 → 2 → 3 → 4)의 4가지이다. www.acmicpc.net 일단 N=1일 때부터 직접 계산해보면서 규칙을 찾아보았다. N=1일 때 1, N=2일 때 1, N=3일 때 2, N=4일 때 4, N=5일 때 8 ... N=1일 경우를 제외하고 2의 (N-2)제곱이 나오는 것을 확인 할 수 있었다. 단순히 print(2**(N-2))를 하면 N의 범위가 최대 10**9이므로 O(10**9)가 되어서 시간초과가 발생한다. 따라서 분할정복을 이용한 거듭제곱을 해서 시간을 줄여야 한다. # 분할정복을 이용한 거듭제곱은 따로 정리해..
www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net (0, 0)에서 (M-1, N-1)까지 이동 가능한 경로의 수를 모두 구해야 하기 때문에 단순히 DFS로는 풀 수 없고, DP를 통해 메모이제이션까지 써야 한다. 1. N * M크기의 지도 m을 입력받고, dp배열을 만들고 -1로 채운다. 2. dp[i][j] = (i, j)까지 이동하는 경로의 수 3. (M-1, N-1)부터 상하좌우 방향을 탐색하며 dp[x][y]에 dfs(nx, ny)값을 더해준다. ->..
www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 이번엔 DFS로 푼 문제이다. dfs함수: m[x][y] = 0을 해줌으로써 방문했다는 표시를 해준다. 전에 올린 문제와 비슷하게 nx, ny에 x + dx[i], y + dy[i]를 넣고 탐색한다. BFS는 nx, ny를 방문하지 않았을 경우, (nx,ny)를 deque에 넣고 방문처리를 해줬는데 DFS는 재귀방식으로 dfs함수를 또 호출한다. 매개변수로 cnt+1을 넘겨줌으로써 현재 단지에 속하는 집의 수를 ..
모르는 사이에 조금씩 조금씩..
