목록깊이 우선 탐색 (6)

맛있는감귤

BOJ : 2583 영역 구하기

문제 : https://www.acmicpc.net/problem/2583출처Olympiad > 한국정보올림피아드시․도지역본선 > 지역본선 2006 > 고등부 2번 저는 맵을 만든 후 사각형 부분은 전부 1로 하고 나머지 0이 되는 부분만 DFS를 이용하여 넓이를 구한 후 벡터에 넣어주고 사이즈( 사각형의 개수)를 출력 한 뒤 정렬하여 넓이를 출력했지만 우선순위 큐에 넣으면 간단하게 해결됩니다. #include <iostream> #include <algorithm> #include <vector> using namespace std; int M,N,K; bool map[102][102]; bool isVisited[102][102]; vector<int> v; int px[..
알고리즘/백준 알고리즘 2017. 3. 3. 16:24
BOJ : 1967 트리의 지름

문제 : https://www.acmicpc.net/problem/1967한 노드를 기준으로 가지고 있는 말단 노드를 쫙 땡겼을 때 가장 긴 녀석의 지름을 구하는 문제입니다.자식 노드가 3개 이상일 수 있다는 것만 조심하시면 DFS로 간단하게 해결 가능합니다.자식 노드의 가중치의 합을 return 하여 기준 노드에서 가장 긴노드, 두 번째 노드를 구해서 더한 값이 지름이 됩니다. #include #include using namespace std; int N, ans=0; vector v[10001]; int dfs(int start){ int fst=0, snd=0, sum; for (auto n : v[start]){ //printf("%d %d\n",start,n.second+len); sum = ..
알고리즘/백준 알고리즘 2017. 3. 3. 16:17
BOJ : 2573 빙산

문제 : https://www.acmicpc.net/problem/2573 시간에 따라 맵이 바뀌는 문제이다. 얼음이 녹을 때 시간마다 -1인줄 알았는데 기준점에서 동서남북 상태에 따라 얼음 융해도가 다르다는 것을 간과한 것이 문제였다. 코드가 더럽게 되었는데 문제점이 있으면 댓글로 지적해주시면 감사하겠습니다. #include <stdio.h> int R,C,cnt=0,time=0; int map[303][303]; bool isVisited[303][303]; int dr[4]={1,-1,0,0}; int dc[4]={0,0,1,-1}; void dfs(int r,int c){ isVisited[r][c] = true; for(int i=0;i<4;i++){ int nr = r+dr[i], ..
알고리즘/백준 알고리즘 2017. 2. 7. 01:10
BOJ : 2468 안전 영역

문제 : https://www.acmicpc.net/problem/2468출처Olympiad > 한국정보올림피아드 > KOI 2010 > 초등부 2번DFS 문제입니다. 잠기는 높이가 0일 때도 포함되는 것을 유념하시길 바랍니다.반복문 인자로 자주 쓰는 i,j,k는 함수 파라미터로 사용하지 말자...ㅠㅠ #include int map[101][101],ans=0,N; int di[4]={1,-1,0,0}; int dj[4]={0,0,1,-1}; bool isVisited[101][101]; void dfs(int ii, int jj, int k, int cnt){ isVisited[ii][jj] = true; for(int i=0;i= 0 && nj >= 0 && ni < N && nj < N && map..
알고리즘/백준 알고리즘 2017. 2. 4. 22:18
BOJ : 1743 음식물 피하기

문제 : https://www.acmicpc.net/problem/1743 github : https://github.com/JEONG-SEUNGWOOK/BOJ/blob/master/1743.cpp 출처 : Olympiad > USA Computing Olympiad > 2007-2008 Season > USACO November 2007 Contest > Bronze 3번 PKU Judge Online좌표 상에 놓여져 있는 가장 큰 음식물 쓰레기 크기를 출력하는 문제. 문제만 더러워졌지 일반적인 완전 탐색 문제다. DFS를 이용해 후딱 풀었다 #include using namespace std; int N,M,K,ans=0,cnt=1; bool map[101][101]; bool isVisited[10..
알고리즘/백준 알고리즘 2017. 1. 17. 13:47
BOJ : 1707 이분 그래프

문제 : https://www.acmicpc.net/problem/1707 github : https://github.com/JEONG-SEUNGWOOK/BOJ/blob/master/1707.cpp 한 노드가 1 또는 0의 값을 가지고 있다고 하면 다음 노드는 반대 값을 가지고 있는 것이 이분 그래프라고 생각하면 된다. 1-0-1-0|0-1 뭐 이런 식으로..? start 노드를 기준으로 DFS를 이용해 다음 노드를 탐색하며 기준 노드와 다음 노드가 다른 값을 가지는지 검사한다. #include #include using namespace std; vector G[20001]; int value[20001]; int V, E; int flag = 1; bool dfs(int start,int f){ va..
알고리즘/백준 알고리즘 2017. 1. 17. 13:42
이전 Prev 1 Next 다음