BOJ (34) 썸네일형 리스트형 BOJ 4963 섬의 개수 - DFS(x,y,cnt)로 넘겼을 때 0ms - BFS(x,y,cnt)로 넘겼을 때 4ms - BFS(x,y)로 넘겼을 때 0ms - w, h의 위치를 잘 보고 입력 받아야 한다. https://www.acmicpc.net/problem/4963 * DFS 풀이 #include using namespace std; int map[52][52]; int visited[52][52]; int w,h,cnt; int dx[8]={-1,0,1,-1,1,-1,0,1}; int dy[8]={1,1,1,0,0,-1,-1,-1}; void dfs(int x, int y, int cnt){ visited[x][y]=cnt; for(int i=0; i=0 && ny>=0 && nx BOJ 2667 단지번호붙이기 - 큐를 이용하여 BFS 탐색하는 기본 문제 - 두번째 풀 때는 단지 내부에 있는 집의 개수를 세기 위해 vector를 이용하려고 했는데 잘 안됐다. 다음 번에는 벡터로 풀어봐야겠다. - DFS 로도 풀어봐야겠다! https://www.acmicpc.net/problem/2667 #include #include #include #include using namespace std; int n, cnt; int map[26][26]; int visited[26][26]; int ans[26*26]; int dx[4]={-1,0,0,1}; int dy[4]={0,-1,1,0}; void bfs(int x, int y, int cnt){ queue q; q.push(make_pair(x,y)); visited[.. BOJ 2468 안전 영역 DFS https://www.acmicpc.net/problem/2468 - BOJ 2667 단지 번호 붙이기와 유사 문제 - DFS로 풀었음 - 사실 처음엔 문제 이해가 되지 않았음. 높이가 주어지는 것이 아니었고, 모든 높이를 고려했을때 섬(?)이 많은 것을 print 하면 된다. - 주어진 입력에서 가장 큰 숫자를 저장하여 그 숫자부터 내림차순으로 탐색하였음. - 높이가 새로 정의 될 때마다 visited 배열 초기화해야한다. #include #include #include using namespace std; int map[110][110]; int visited[110][110]; int dx[4]={-1,0,0,1}; int dy[4]={0,-1,1,0}; int n, cnt; int ans[110*.. BOJ 10026 적록색약 - BFS 함수를 두 번 호출 하여 해결. - 첫번째 호출 시 적록색약 아닌 사람 계산 후 두번째 호출 위해 초기화 할때 R을 G로 변경하고 두번째 호출 때 G와 B만 남으므로 그대로 BFS 계산 https://www.acmicpc.net/problem/10026 BOJ 2583 영역 구하기 DFS - Y 좌표가 뒤집어져 있어서 input 할 때 헷갈렸다. - DFS, recursion으로 해결 - 영역 갯수, 영역 크기 모두 구해야 한다. https://www.acmicpc.net/problem/2583 #include #include using namespace std; int board[110][110]; int visited[110][110]; int ans[110*110]; int dx[4]={-1,0,0,1}; int dy[4]={0,-1,1,0}; int m, n, k; void dfs(int x, int y, int cnt){ visited[x][y]=cnt; //영역번호. for(int i=0; i=0 && nx=0 && ny BOJ 1697 숨바꼭질 BFS - BFS - 큐 이용 - for문 + dx 좌표 잡는 대신, 가능한 3번의 경우를 모두 큐에 넣어버림 https://www.acmicpc.net/problem/1697 #include #include #include using namespace std; int visited[100000]={0}; int t[100000]={0}; // 시간 측정 int main(){ int st, en; int cnt=0; scanf("%d %d", &st, &en); visited[st]=1; // 현재 위치를 1로 // BFS queue q; q.push(st); visited[st]=1; while(!q.empty()){ int cur = q.front(); q.pop(); // 3방향 // cur - 1 int.. BOJ 1012 유기농 배추 DFS - DFS + cnt 구하기 - 기본적인 문제. 섬의 갯수(BOJ 4963)와 매우 유사한 문제 https://www.acmicpc.net/problem/1012 #include #include using namespace std; int field[55][55]; // 배추 밭 int visited[55][55]; int m,n; int dx[4] = {0, 0, -1, 1}; int dy[4] = {-1, 1, 0, 0}; //DFS void dfs(int x, int y, int cnt){ visited[x][y]=cnt; for(int i=0; i=0 && nx=0 && ny BOJ 1926 그림 - DFS https://www.acmicpc.net/problem/1926 - BFS DFS 모두 가능하지만 DFS를 이용하여 풀었다 - 그림의 갯수는 cnt를 이용하여 출력할 수 있지만 가장 큰 그림의 크기를 구하기 위해 ans[502*502]를 선언했다. - 아직도 DFS가 헷갈려 ㅠㅠ #include #include using namespace std; int board[502][502]; int visited[502][502]; int n, m; // 1st input int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; int ans[502*502]={0}; void dfs(int x, int y, int cnt){ visited[x][y] = cnt; // 방.. 이전 1 2 3 4 5 다음 목록 더보기