본문 바로가기

전체 글

 (336)
백준 13549 숨바꼭질3 (C++) 0-1 BFS, 다익스트라, 우선순위 큐 등 많은 방법으로 풀 수 있지만 한 번도 안해본 0-1 BFS를 사용해 풀어보았다. 이 문제의 출제 의도이자 최적화가 잘되어있어 0ms만에 문제를 풀어낼 수 있다. 0-1 BFS의 대한 알고리즘은 https://tigerfrom2.tistory.com/8 0-1 BFS 너비 우선 탐색 0-1 BFS는 기본적으로 BFS와 동일하지만 간선의 이동 비용이 0과 1인 경우를 이야기한다. 때문에 적은 비용으로 이동하기 위해서는 비용이 0인 간선으로 이동하는 것을 최대한 장려해야한다. 0-1 bf tigerfrom2.tistory.com #include #include #include #define MAX 100001 using namespace std; int N, M; ..
0-1 BFS 너비 우선 탐색 0-1 BFS는 기본적으로 BFS와 동일하지만 간선의 이동 비용이 0과 1인 경우를 이야기한다. 때문에 적은 비용으로 이동하기 위해서는 비용이 0인 간선으로 이동하는 것을 최대한 장려해야한다. 0-1 bfs는 덱을 사용하여 구현할 수 있다. 지금까지 스택, 큐는 자주 사용했지만 덱은 다뤄본 적이 거의 없다. 먼저 덱(deque)은 큐와 비슷하지만 왼쪽과 오른쪽 모두 pop이 가능한 자료구조이다. 알고리즘은 다음과 같다. 1. 현재 덱의 현재 노드를 꺼내본다. 2. 인접노드를 살펴본다. 3. 인접노드로 넘어가는데 비용이 0이면 front에 1이면 back에 삽입한다. -> why? 왜 프론트와 백에 따로 저장을 할까? 이것은 본문 두번째 줄의 비용이 0인 간선 이동을 장려해야하기 때문이다. 2*x 는 비용..
Git, 기본사용법 (GitBash, pull, push) Git이란 프로그래머들이 협업할때 서로 복붙해서 코드를 보낼 필요 없이 서로 코드를 공유하고 합쳐주는 소프트웨어이다. 그러나 "알려진 오류의 원인" 이라는 말이 있을 정도로 쓰는법이 어렵다. 기업 우대조건에도 Git 사용에 자유로우신 분 문구가 자주 써있다. 이번에 팀플을 하면서 깃허브를 다른 사람과 사용할 일이 생겨서 벼락치기 중이다. 난 Git은 여러 관리 프로그램이 있는데 난 Git Bash를 사용한다. 나도 거의 메모, 정리용으로 적는 거라 틀린 내용 얼마든지 있을 수 있다. 1. git status 지금 깃과 연결된 폴터의 파일들과 허브의 파일들을 비교해 바뀐 점이 있는지 체크한다. 2. git add . 아직 정확히 모르겠는데 커밋 전 행동으로만 알고 있다. 3. git commit -m "메..
백준 7576번 토마토(C++) 예전에 풀었던 문제이지만 다시한 번 해보았다. 예전의 코드는 구글링의 다른 사람의 코드를 도움 받았기 때문이다. 그리고 BFS의 좋은 예제이다. 먼저 토마토 1이 있으면 하루에 4방향으로 증식한다. 증식한 토마토는 또 4방향으로 증식하게된다. DFS로 계산하면 한 방향으로만 가버리기 때문에 적절하지 않다. 결국 BFS를 통해 첫 1부터 제일 떨어져 있는 거리까지의 최소거리(최소일수)를 구하는 문제로 귀결된다. 그러나 여기서 중요한 것은 1이 한군데만 존재하지 않는다는 것이다. 즉, 두군데 이상의 1에서 동시에 증식을 시작해야한다. 그림으로 표현하면 이런식이다. 때문에 DFS는 절대(적어도 내 기준에선) 사용할 수 없다. 알고리즘은 이러하다. 1. 처음 토마토가 심어져 있는 좌표를 큐에 삽입. 2. 삽입된..
백준 1697 숨바꼭질 (C++) #include #include #include #include #include #include #define MAX 51 using namespace std; queue Q; int x, y; bool visited[100001] = {false,}; void BFS() { Q.push(make_pair(x, 0)); visited[x] = true; while (!Q.empty()) { int X = Q.front().first; int T = Q.front().second; Q.pop(); if (X == y) { cout -1 && X - 1 < 100001 && visited[X - 1] == false) { Q.push(make_pair(X - 1, T + 1)); visited[X - 1] ..
백준 1707번 이분 그래프(C++) #include #include #include #define MAX 20001 using namespace std; int V, E; int x, y; int check = 0; vector vertex[MAX]; bool visited[MAX] = { false, }; int vertexCol[MAX] = { 0, }; void setgraph() { cin >> V >> E; for (int i = 0; i > x >> y; vertex[x].push_back(y); vertex[y].push_back(x); } } void DFS(int here) { if (visited[here] == true) return; visited[here] = true; for (int..
그래프 이론 - 깊이 우선 탐색: DFS 그래프란? 우리 일상생활에서 흔히 볼 수 있는 그래프로 도로, 네트워크, 버스 노선도 등을 들 수 있습니다. 그래프를 탐색하거나 분석할 때 그냥 일일히 방문하는 방법도 있겠지만 프로그래머들은 다른 방법이 없을까 고민했습니다. DFS - 깊이 우선 탐색 깊이 우선 탐색이란 한 노드를 선택하고 그 노드를 타고 노드의 끝까지 매우 deep 하게 파고들어갑니다. 방문한 곳에는 항상 방문표시를 합니다. 그림으로 보면 1번 노드부터 시작했습니다. 가장 인접한 노드(자식노드) 2, 5중 더 작은 번호로 가는 것으로 여기선 가정하겠습니다. 2번 노드 도착 -> DFS 그럼 2의 인접노드 3, 4 중 더 작은 번호로 갑니다. 3번 노드 도착 -> DFS 그런데 3번노드에서 보니 자식노드가 없습니다. 그렇다면 위로 돌아가..
백준 1966번 프린터 큐(C++) #include #include #include #include using namespace std; int S, N, M; int x; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> S; for (int i = 0; i > N >> M; int cnt = 0; for (int j = 0; j > x; Q.push(x); q.push(make_pair(j, x)); } while (!q.empty()) { int index = q.front().first; int value = q.front(..

티스토리툴바