본문 바로가기

[PS] 문제풀이/백준39

[ 백준 1260 ] DFS와 BFS (C++, DFS-BFS) [문제보기] 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net [해결과정] DFS, BFS 사용 [소스코드] #include #include #include #include #include using namespace std; int n, m, s; int check[10005]; vector v[10005]; queue q; void dfs(int node){ cout s; for(int i=0; i> a >> b; v[a].push_back(b); v[b].push_ba.. 2021. 10. 22.
[ 백준 9095 ] 1, 2, 3 더하기 (C++) [문제보기] [해결과정] 재귀 사용 [소스코드] #include #include using namespace std; int t; int n; int arr[3] = {1,2,3}; int result; void func(int val, int sum){ // 기저조건 if(val == sum){ result++; return; }else if(val t; while(t--){ cin >> n; // 완전탐색 result = 0; func(n,0); cout 2021. 10. 22.
[ 백준 1929 ] 소수 구하기 (C++, 에라토스테네스의 체) [문제보기] [해결과정] 에라토스테네스의 체 사용 -> 각 해당하는 수가 소수가 아닐 경우 그에 대한 배수는 모두 소수 처리하는 것 [소스코드] #include #include using namespace std; int n, m; int prime[1000005]={0,1,0,}; void isPrime(){ for(int i=2; i n >> m; isPrime(); for(int i=n; i 2021. 10. 22.
[ 백준 10868 ] 최솟값 (C++, 세그먼트 트리) [문제보기] [해결과정] - 세그먼트 트리 활용 [소스코드] #include #include #include #include #include using namespace std; typedef long long ll; #define MAX 400005 int n, m, a, b; ll minTree[MAX*10]; ll node[MAX]; // init(배열, 위치, 시작점, 끝점) ll minInit(ll arr[], ll treeIdx, ll dataIdxL, ll dataIdxR) { if (dataIdxL == dataIdxR) return minTree[treeIdx] = arr[dataIdxL - 1]; ll mid = (dataIdxL + dataIdxR) / 2; return minTree.. 2021. 4. 17.
[ 백준 2357 ] 최솟값과 최댓값 (C++, 세그먼트 트리) [문제보기] [해결과정] - 세그먼트 트리 활용 1. minTree, maxTree 구별 2. 각각 init함수와 query함수 작성 [소스코드] #include #include #include #include #include using namespace std; typedef long long ll; #define MAX 400005 int n, m, a, b; ll minTree[MAX*10]; ll maxTree[MAX*10]; ll node[MAX]; // init(배열, 위치, 시작점, 끝점) // init_최소 트리 ll minInit(ll arr[], ll treeIdx, ll dataIdxL, ll dataIdxR) { if (dataIdxL == dataIdxR) return minTre.. 2021. 4. 17.
[ 백준 11659 ] 구간 합 구하기 (C++, 세그먼트 트리) [문제보기] [해결과정] - 세그먼트 트리 사용 [소스코드] typedef long long ll; #include #include #include #include using namespace std; ll node[400000]; ll tree[400000]; // init(배열, 위치, 시작, 끝) ll init(ll arr[], ll treeIdx, ll dataIdxL, ll dataIdxR){ if(dataIdxL == dataIdxR) return tree[treeIdx] = arr[dataIdxL-1]; ll mid = (dataIdxL + dataIdxR) / 2; return tree[treeIdx] = init(arr, 2*treeIdx, dataIdxL, mid) + init(arr,.. 2021. 4. 17.
[ 백준 15686 ] 치킨 배달 (C++) [문제보기] [해결과정] 1. 좌표 구조체를 생성한다. 2. 집 좌표 배열, 치킨 집 좌표 배열을 생성 - ★집은 2N개이다. (가장 많이 틀리는 부분) 3. 조합 (dfs) 수행 - M개의 치킨 집 고르기 4. 기저조건 상태라면, 집들을 돌며 치킨 집과의 거리를 구하고 가장 작은 거리를 sum에 더한다. 5. sum 값과 ans를 비교하여 ans 갱신 [소스코드] 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 .. 2020. 6. 3.
[ 백준 14502 ] 연구소 (C++) [문제보기] [해결과정] 1. 큐(bv) 생성 후 바이러스 좌표를 넣기. 2. 큐(q) 생성 3. dfs로 벽 3개 세우기 (조합 사용) - 세운 벽은 큐(q)에 넣기 4. 기저조건에 맞는 상태면 바이러스 활성화 해서 모두 퍼뜨리기 5. 가장 많은 빈공간이라면 답 갱신 6. 동작 후 맵은 원복, 방문 체크는 초기화 [소스코드] 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 7.. 2020. 6. 3.
[ 백준 17144 ] 미세먼지 안녕! (C++) [문제보기] [해결과정] 1. 공기청정기 위치를 저장할 구조체 생성 2. 기존 맵 1개, 기존 맵에서 먼지가 퍼지는 것을 저장할 맵 1개 생성 3. input 4. 기존 맵(map)을 돌며 먼지가 있으면 퍼지는 것을 저장할 맵(arr)에 계산 하여 저장 5. 주변에 퍼질 수 있는 공간에 퍼뜨리고, 그 수를 별도 저장. 6. 다 퍼뜨리고 해당 공간 계산 7. map에 arr맵을 복사하고, arr맵 초기화. 8. 위쪽 공기청정기, 아래쪽 공기청정기 순차적으로 수행 (반시계 경우, 시계방향으로 가며 칸을 끌어당기기) (시계 경우, 반시계방향으로 가며 칸을 끌어당기기) [소스코드] 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 2.. 2020. 6. 3.
[ 백준 10026 ] 적록색약 (C++) [문제보기] [해결과정] 1. input -> n, arr 입력받기 2. 정상인 사람이 볼 때, -> arr을 순회하며, 방문체크가 안되있는 좌표를 queue에 넣고 bfs수행, -> 진입할 때, 방문체크 하고 gNum++ (그룹수) -> bfs(0) 플래그 0으로 진입 3. bfs(0) -> bfs수행 하는데, flag가 0인 부분으로 진입 4. 적록색약인 사람이 볼 때, -> 먼저 check 배열 초기화, gNum = 0으로 변경 -> 맵을 순회하며 R을 G로 바꾸거나 혹은 G를 R로 다 바꿔버림. 5. 적록색약인 사람이 볼 때 기능 실행 -> arr을 순회하며, 방문체크가 안되있는 좌표를 queue에 넣고 bfs수행, -> 진입할 때, 방문체크 하고 gNum++ (그룹수) -> bfs(1) 플래그 .. 2020. 3. 18.
[ 백준 17142 ] 연구소3 (C++) [문제보기] [해결과정] 1. input -> n, m, arr 맵 --> 빈칸(0)의 갯수 카운트 하기 : if(arr 맵 == 0) k++ 2. DFS 완전탐색 -> 맵을 순회하며, 비활성바이러스를 발견하면, -1로 변경후 다음 DFS 수행 3. DFS 수행 중 Count 개수가 m과 같다면, 기능 실행 -> check 함수 -1로 초기화 -> DFS를 통해 활성바이러스로 바꾼 좌표를 큐에 삽입 (맵==-1) -> BFS() 수행 4. inf (0을 1로 바꾼 개수) , times (걸린 시간) 변수 선언 5. while(!q.empty()) 수행 -> 4방향 탐색하며, check == -1 && arr!=1 인 곳 방문 -> 만약 arr=0 이면 방문할 때 시간으로 times 갱신, inf++ 수행.. 2020. 3. 18.
[ 백준 16236 ] 아기 상어 (C++) [문제보기] [해결과정] 1. input ( n , arr에 맵 입력받기 ) -> 주의할점! 9는 상어의 초기 위치이다. 상어 위치를 다른 변수에 담고 맵에 9가 아닌 0으로 넣는다. 2. solution 수행 (1) 현재 상어 위치를 큐에 담는다 (2) BFS 수행 -> BFS를 돌며 현재 상어크기보다 같거나 작으면 진입 -> 만약 현재 상어크기보다 작으면 잡을 수 있는 물고기 ableFish++; -> 그리고 map값에 *=-1 하며 음수로 만들기 (음수인 곳은 잡을 수 있는 물고기란 뜻) -> minFish에 가장 작은 이동거리 저장시키기 (3) BFS가 끝나면, 맵 처음부터 끝까지 순회 -> 순회하며 음수인 곳을 가장 처음 만나는 곳이 잡아야 하는 물고기. -> 물고기를 잡고, 상어가 잡은 물고기.. 2020. 3. 11.
[ 백준 1076 ] 저항 (C++) [문제보기] [해결과정] 1. input : 3가지 색깔 (string) 2. 배열을 만들고, 색깔을 인자로 받고 값을 리턴하는 함수를 만들어, 각각의 색에 return 값을 만들어 준다. 3. 1번째와 2번째 배열 값들은 그대로 출력해주고, 3번째 배열 값 만큼 0을 반복하여 출력한다. -> 예외1 : 1번째 배열 값이 0인 경우, 2번째 배열 값만 출력 -> 예외2 : 1번째 배열 값과 2번째 배열 값이 0인 경우 0을 출력 [소스코드] 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53.. 2020. 2. 29.
[ 백준 14503 ] 로봇 청소기 (C++) [문제보기] [해결과정] 1. input : n, m + 로봇 좌표 + 맵 2. 로봇 좌표와 방향을 담는 구조체와 큐 생성 후 큐에 좌표 넣기 3. 반복문 -> 큐에서 꺼낸 좌표가 청소되어있지 않다면 청소. -> 해당 좌표부터 왼쪽을 확인하며, 청소되어있지 않다면 진입. -> 만약 진입했다면 반복문 종류 후 continue; -> 만약 4방향 모두 청소되어있지 않다면 뒤로 이동... -> 만약 뒤로 이동할 수 없다면 전체 반복문 종료 [소스코드] 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52.. 2020. 2. 28.
[ 백준 2851 ] 슈퍼 마리오 (C++) [문제보기] [해결과정] 1. input : arr(int형) 배열에 10개 버섯 담기 2. sum+=arr[i] 를 진행 -> 만약 절대값 sum+arr[i] -100 arr[i]; for (int i = 0; i 2020. 2. 27.

티스토리툴바