본문 바로가기

분류 전체보기

 (386)
백준 7562 나이트의 이동(C++) #include #include #define MAX 301 using namespace std; int dX[] = { 2,-2, 1,-1, 2 , -1 , -2 , 1}; int dY[] = { 1,-1,2,-2, -1 , 2 , 1 , -2}; int dis[MAX][MAX] = { 0 ,}; bool visited[MAX][MAX] = { false, }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); int N; int Size; int nightX, nightY; int desX, desY; cin >> N; for (int i = 0; i > Size >>..
백준 1261번 알고스팟(C++) 벽을 부수고 이동한다는게 무슨 말인지 모를 수 있지만 결국 비용이 1인길을 선택하느냐 0인길을 선택하느냐의 차이이다. 우리는 목적지까지 최소한으로 이동해야하기 때문에 최대한 0인부분을 잘 이용해야한다. 그렇기 때문에 이 문제는 0-1 BFS 최소비용 or 다익스트라 문제이다. 처음에는 아래 코드로 했다가 예제에서 틀렸다. #include #include #include #define MAX 1001 using namespace std; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; deque Q; int dis[MAX][MAX]; int wall[MAX][MAX]; bool visited[MAX][MAX] = { false, }; void BFS(int N, i..
백준 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..

티스토리툴바