본문 바로가기
반응형

Algorithm_BOJ(백준)/깊이,너비우선탐색(DFS,BFS)

 (47)
[백준 2606 c++ VO] 바이러스 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 #define _CRT_SECURE_NO_WARNINGS #include #include // c 문법 헤더파일 #include // 동적배열 라이브러리 #include using namespace std; // cin,cout 편하게 사용 라이브러리 // [백준 2606 c++ VO] 바이러스 // 문제: 1번 컴퓨터를 통해 감염되는 컴퓨터의 갯수 구하기 // 점근1: : 기본 인접행렬 dfs : 연결된 노드탐색 // 풀이: // 인접행렬 만들..
[백준 14500 c++ O] 테트로미노 문제 링크 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 접근 // [백준 14500 c++ O] 테트로미노 // 문제: 가능한 5종류의 칸의 합 중 테트로미노 각 칸의 합의 최대값 구하기 // 접근: 칸의 개수 4개 -> depth가 4인 dfs 생각 -> 근데 ㅗㅓㅏㅜ 는 dfs로 탐색 불가능한 모양 이어서 따로 계산 문제 풀이 // 풀이: // 뎁스가4 인 완전탐색 dfs로 테트로 미노의 최댓값 갱신 // ㅏㅓㅗㅜ 모양은 중심칸의 ..
[백준 5567 c++ V] 결혼식 문제 링크 https://www.acmicpc.net/problem/5567 5567번: 결혼식 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2,3,4 3명의 친구를 결혼식에 초대한다. www.acmicpc.net 문제 접근 // [백준 5567 c++ V] 결혼식 // 문제: 그래프 로 이어진 상근이 친구의 친구등 까지 명 수 세기 // 접근: 인접리스트 양방향 그래프로 bfs 탐색 문제 풀이 // 풀이: // 인접리스트 양방향 그래프 입력 // bfs 탐색으로 상근이 친구 탐색하며 방문배열과 친구배열 최신화 // 최신화된 친구배열을 이용해 이접리스트 탐색하며 친구의 친구 탐색하며 방문처리 //..
[백준 2644 c++ VV] 촌수계산 문제 링크 www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net 문제 접근 // 문제: 가족 구성원 사이의 촌수 계산 ,가족을 노드라 하고 찾고자 하는 가족의 촌수 계산하고 없으면 -1출력 탐색 문제 // 가족 관계는 양방향 그래프라 생각해야 함 // 접근1: 가족을 노드라 하고 기본 인접행렬 그래프 dfs탐색 , 인접행렬은 벡터로 구현 문제 풀이 // 풀이: 가족관계 벡터 인접행렬에 저장 // 찾고자 하는 가족노드에서 dfs 시작하고 // 다른 풀..
[백준 1325 c++ V] 효율적인 해킹 문제 링크 www.acmicpc.net/problem/1325 a 로의 단일방향 엣지를 의미 // 접근1: 컴퓨터를 노드라 생각하면 각 노드에서의 dfs로 탐색 개수 구함 문제 풀이 // 풀이: 각 노드에서의 기본 dfs // 컴퓨터의 수가 최대값보다 크면 check벡터 clear후 저장 // 컴퓨터의 수가 최댓값과 같으면 check벡터에 추가 // 벡터정렬 후 출력 주의 // 컴퓨터 번호 1부터 시작 개념 소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include // c 문법 헤더파일 #include // c++ 문자열 클래스 #include // 동적배열 라이브러리 #include #include #include #include // sort와 unique 사..
[백준 1743 c++ O] 음식물 피하기 문제 링크 www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ 10,000)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진 www.acmicpc.net 문제 접근 // 문제: 배열중 인접해있는 음식물의 크기의 합이 가장 큰 음식물의 크기를 출력 // 접근: 4방향인접하면 하나의 음식물로 본다 -> 기본 dfs 탐색 문제 풀이 // 풀이: 배열의 크기와 음식물 위치 입력 // 기본 완전탐색 dfs // 음식물의 최대크기 최신화 // 음식물 최대크기 출력 주의 // 배열의 인덱스 1부터 시작하는 것으로 입력 ..
[백준 2210 c++ V] 숫자판 점프 문제 링크 www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 문제 접근 // 문제: 숫자배열에서 4방향으로 탐색을 하며 나오는 6자리 서로다른 숫자의 개수를 구하는 문제 // 접근: 4방향 탐색이어서 dfs,bfs중 하나로 탐색하는데 방문 한곳 또 해서 방문배열 불필요, 중복된숫자 거르기 위해 set 자료형 사용 문제 풀이 // 풀이: 배열 입력 // 완전탐색 dfs // 6번째 depth 에서 숫자를 set 자료형에..
[백준 2644 c++ V] 촌수계산 문제 링크 www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net 문제 접근 // 문제: 부모와 자식의 촌수를 1로 해서 주어진 두 사람의 촌수를 구하는 문제 // 접근: 인접행렬방식 dfs 로 부모와 자식의 관계를 양방향 그래프로 표현 문제 풀이 // 풀이: 벡터배열로 2차원 배열에 양방향 그래프 입력 // 찾기만 하고 초기화 않해줘도 되는 기본 dfs 이용해서 인접리스트 그래프 탐색 주의 개념 소스코드 #define _CRT_SECURE_NO_WA..
반응형

티스토리툴바