일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 클린코드
- 책리뷰
- #알고리즘 #백준 #12094 #백준12094 #algorithm #baekjoon #baekjoon12094 #C++
- #알고리즘 #백준 #2616 #백준2616 #algorithm #baekjoon #baekjoon2616 #Java
- #알고리즘 #백준 #15684 #백준15684 #algorithm #baekjoon #baekjoon15684 #C++
- #알고리즘 #백준 #17140 #백준17140 #algorithm #baekjoon #baekjoon17140 #C++
- 개발서
- #알고리즘 #백준 #17406 #백준17406 #algorithm #baekjoon #baekjoon17406 #C++
- #알고리즘 #백준 #3190 #백준3190 #algorithm #baekjoon #baekjoon3190 #C++
- #알고리즘 #algorithm #프로그래머스 #2020카카오공채 #블록이동하기 #programmers #C++
- 개발자취미
- #알고리즘 #백준 #2580 #백준2580 #algorithm #baekjoon #baekjoon2580 #Java
- #알고리즘 #백준 #17136 #백준17136 #algorithm #baekjoon #baekjoon17136 #C++
- #알고리즘 #algorithm #프로그래머스 #2020카카오공채 #문자열압축 #programmers #C++
- #알고리즘 #백준 #17837 #백준17837 #algorithm #baekjoon #baekjoon17837 #C++
- #알고리즘 #백준 #15683 #백준15683 #algorithm #baekjoon #baekjoon15683 #C++
- #알고리즘 #백준 #17472 #백준17472 #algorithm #baekjoon #baekjoon17472 #C++
- #알고리즘 #백준 #1987 #백준1987 #algorithm #baekjoon #baekjoon1987 #Java
- #알고리즘 #백준 #14888 #백준14888 #algorithm #baekjoon #baekjoon14888 #C++
- CleanCode
- #알고리즘 #백준 #1260 #백준1260 #algorithm #baekjoon #baekjoon1260 #Java
- 스레드 #동시성 #thread #process #
- #알고리즘 #백준 #2352 #백준2352 #algorithm #baekjoon #baekjoon2352 #C++
- #알고리즘 #algorithm #프로그래머스 #2020카카오공채 #외벽점검 #programmers #C++
- #알고리즘 #백준 #4386 #백준4386 #algorithm #baekjoon #baekjoon4386 #C++
- #알고리즘 #algorithm #프로그래머스 #2020카카오공채 #괄호변환 #programmers #C++
- #알고리즘 #백준 #1525 #백준1525 #algorithm #baekjoon #baekjoon1525 #C++
- #알고리즘 #백준 #5214 #백준5214 #algorithm #baekjoon #baekjoon5214 #C++
- #알고리즘 #백준 #2573 #백준2573 #algorithm #baekjoon #baekjoon2573 #C++
- #알고리즘 #백준 #1793 #백준1793 #algorithm #baekjoon #baekjoon1793 #C++
Archives
- Today
- Total
개발자 일기장.
백준 5214. 환승 본문
[백준 5214] 환승
문제 알고리즘
- bfs문제
- 메모리 관리
풀이방법
bfs를 통해서 문제를 푸는데 메모리가 터지는 것을 염두하고 문제를 짜야한다.
- 처음에는 일반적인 bfs인줄 알고 풀었는데 바로 메모리가 터졌다.
- 보통 1억개가 넘어가면 300MB가 넘어간다는 이야기를 이 문제를 풀면서 알았다.(100,000개에 100,000개씩 연결이 되면 100억 정도되는데 그러면 메모리가 터져버린다.)
- 해결책은 1~100000까지는 일반적인 역, 100001 ~ 101000까지는 하이퍼루프 번호로 정해서 연결시켜버리는 것이다.
이해를 돕는 사진
핵심 코드
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX 100000 + 1
vector<int> adj_list[MAX + 2000];
bool visited[MAX + 2000];
int N, K, M;
int bfs() {
queue<pair<int, int>> q; // (station, cnt);
q.push({ 1, 1 });
visited[1] = true;
while (!q.empty()) {
int curStation = q.front().first;
int curCnt = q.front().second;
q.pop();
if (curStation == N) {
return curCnt;
}
for (int i = 0; i < adj_list[curStation].size(); i++) {
int nextStation = adj_list[curStation][i];
if (!visited[nextStation]) {
if (nextStation > N) // 더미역
q.push({ nextStation, curCnt });
else {
q.push({ nextStation, curCnt + 1 });
visited[nextStation] = true;
}
}
}
}
return -1;
}
int main() {
// input
int key;
cin >> N >> K >> M;
for (int i = 1; i <= M; i++) {
for (int j = 0; j < K; j++) {
scanf("%d", &key);
adj_list[MAX + i].push_back(key);
adj_list[key].push_back(MAX + i);
}
}
// solution & output
cout << bfs() << "\n";
return 0;
}
문제 후 느낀점
- 문제를 꼼꼼히 읽어봐야함을 느꼈다.
'취업 > Algorithm.' 카테고리의 다른 글
백준 3190. 뱀 (0) | 2020.05.30 |
---|---|
백준 2616. 소형기관차 (0) | 2020.05.30 |
백준 2580. 스도쿠 (0) | 2020.05.30 |
백준 2532. 반도체 설계 (0) | 2020.05.30 |
백준 1987. 알파벳 (0) | 2020.05.30 |