본문 바로가기

분류 전체보기

 (203)
6593번 상범 빌딩 BFS 기본 문제. x,y,z를 1씩 증가, 감소시키면서 출구 'E'를 찾으면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 11..
1719번 택배 알고리즘 분류에는 다익스트라로 되어있지만 모든 정점에서 모든 정점으로 가는 경로를 구해야하므로 플로이드 와샬로 풀었다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include #define INF 987654321#define MAX 201 using namespace std; int n,m;int V[MAX][MAX];int map[MAX][MAX]; void solved(){ int d[MAX][MAX]; for(int i=1;i
7562번 나이트의 이동 기본적인 BFS문제. 위, 아래, 왼쪽, 오른쪽으로 움직이던 기존 문제들과는 달리 이번에는 8개의 방향으로 움직인다. 이 표시만 잘해주고 BFS 돌려주면 해결! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 #include #include #include #define visited true #define Non_visited false #define MAX 301 using..
1956번 운동 플로이드 와샬 문제. 플로이드 와샬을 통해 구한 i에서 j로 가는 값은 어디를 지나든 최솟값을 나타내기 때문에 그 반대인 j에서 i로 가는 값이 존재하면 싸이클을 이루게 된다. 따라서 i->j 와 j->i 로 가는 값을 구하고 더한 최솟값을 구하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 #include #include #define INF 987654321 #define MAX 401 using namespace ..
2458번 키 순서 플로이드 와샬 문제. 플로이드 와샬은 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다. 즉, 최단 경로가 존재한다는 것은 갈 수가 있다는 것이고 이 문제에서 그 말은 키를 비교할 수 있다는 것이다. 이 문제의 예시 답은 1, 4번만 자신의 키 순서를 알고 있다. 플로이드 와샬을 실행하게 되면 4번은 2번과 6번에 갈 수 있고 1번과 3번, 그리고 5번은 모른다. 이 상황에서 1번을 기준으로 4번으로 가는 길이 존재하고 3번을 기준으로 4번으로 가는 길이 존재하고 5번을 기준으로 4번으로 가는 길이 존재한다면 4번의 키가 몇 번째인지 알 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 ..
11054번 가장 긴 바이토닉 부분 수열 11053번을 풀면 쉽게 풀 수 있는 DP문제. 1. 0부터 N-1까지 증가하는 부분 수열을 구한다. 2. N-1부터 0까지 증가하는 부분 수열을 구한다. 3. 0부터 N-1까지 구한 두 부분 수열의 값을 더하면서 최댓값을 찾는다. (가장 긴 바이토닉 부분 수열이다) 4. 이때 해당 원소가 중복되기 때문에 최댓값에서 -1을 해준다. ex) num -> 1 2 3 2 1 dp1 -> 1 2 3 2 1 dp2 -> 1 2 3 2 1 dp1+dp2 = 6(최댓값), 원소 3이 중복되므로 -1, 정답은 5. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 4..
1520번 내리막 길 DP 문제로 분류되어 있지만 DP + DFS 문제이다. 1. cnt 배열을 -1로 초기화하고 DFS를 통해 cnt[M-1][N-1]까지 길을 찾은뒤 돌아오면서 겹치는 다른 길을 찾는다. 찾게 되면 cnt 값을 더해주면서 위치 (0,0)까지 오면 그 값이 정답이 된다. (cnt 배열을 -1로 초기화하는 이유 : https://www.acmicpc.net/board/view/14670) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 #include #include #define MAX..
7576번 토마토 기본적인 BFS 문제. 1. 큐에 저장한 익은 토마토의 위치를 꺼내 네 방향의 상태를 확인한다. 2. 익지 않은 토마토가 있다면 익은 토마토가 되고 토마토가 없다면 패스한다(return). 3. 1,2 과정을 반복하여 모든 토마토가 익는 날짜를 구한다. 4. 모든 과정이 끝난 후 익지 않은 토마토가 있다면(solved 함수) -1을 출력하고 그렇지 않다면 다 익은 날짜(제일 큰 cnt값)를 출력한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 6..

티스토리툴바