Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 그리디
- 구현
- sw expert academy
- 삼성 기출
- 동적 계획법
- C++
- 소수
- 알고리즘
- 완전탐색
- 맛집
- 브루트포스
- BOJ
- koitp
- Algorithm
- 백트래킹
- 해커랭크
- 스택
- dfs
- 시뮬레이션
- BFS
- 삼성 SDS 대학생 알고리즘 특강
- PS
- DP
- 잠실
- 백준
- SWEA
- 에라토스테네스의 체
- hackerrank
- dynamic programming
- 다이나믹 프로그래밍
Archives
- Today
- Total
펭로그
[C++] 삼성 SDS KOITP 보물찾기 본문
문제링크 : https://koitp.org/problem/SDS_TEST_TREASURE
[삼성 SDS 대학생 알고리즘 특강 사전 테스트 B Type 1번 문제]
DFS로 풀게되면 무조건 시간초과가 나게되서 BFS로 풀어야하는 문제이다.
최단거리를 찾는 동시에 이동한 거리를 dist 배열을 따로 만들어서 별도로 저장했다.
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 | // KOITP_SDS_Btype_01 #include <bits/stdc++.h> using namespace std; int main() { // freopen("../input.txt", "r", stdin); int T; cin >> T; for (int t = 1; t <= T; t++) { int ruin, numOfClue, remain, result; cin >> ruin >> numOfClue >> remain; vector<vector<bool>>clue(ruin + 1, vector<bool>(ruin + 1, false)); vector<bool>visited(ruin + 1, false); vector<int> queue; vector<int> dist(ruin+1); int input1, input2; for (int i = 0; i < numOfClue; i++) { cin >> input1 >> input2; clue[input1][input2] = true; } visited[1] = true; dist[1] = 0; queue.push_back(1); while(!queue.empty()){ int cur = queue.front(); queue.erase(queue.begin()); for(int i = 1; i <= ruin; i++){ if(clue[cur][i] && !visited[i]){ visited[i] = true; dist[i] = dist[cur] + 1; queue.push_back(i); if(i == ruin) goto OUT; } } } OUT: result = dist[ruin] == 0 || dist[ruin] > remain? -1 : dist[ruin]; cout << "#" << t << " " << result << "\n"; } return 0; } | cs |
'Study > PS(Algorithm)' 카테고리의 다른 글
[C++] 삼성 SDS KOITP 오래된 계산기 (시간초과) (0) | 2018.07.23 |
---|---|
[C++] 삼성 SDS KOITP 큰수만들기 (0) | 2018.07.22 |
[C++] 백준 BOJ 10799 쇠막대기 (0) | 2018.07.20 |
[C++] 삼성 SDS KOITP 전화상담 (3) | 2018.07.20 |
[C++] 삼성 SDS KOITP 고장난시계 (0) | 2018.07.19 |
Comments