홍시홍의 프로그래밍

분류 bfs, 크루스칼 요구사항 다리를 만들어서 섬들을 연결 할 때, 최소한의 수로 모든 섬 연결하기 -> 모든 노드를 연결하되, 최소로 연결하기 -> 최소스패닝트리 풀이 1. 각 섬에 번호 넣기 2. 섬에서 섬으로 연결되는 다리 숫자구하기 3. 다리 숫자 별 정렬 4. Union-Find #include //#include #include //#include "Windows.h" #include #include #include #include using namespace std; struct go{ int x; int y; int dist; }; int n,m; int ccnt=0; int map[11][11]; int visit[11][11]; int dr[4] = {-1,0,1,0}; int dc[..

분류 dfs, 구현 요구사항 각 라운드별 선수의 타율이 주어졌을 때, 최고 점수를 얻을 수 있도록 타순 정하기 풀이 1. 타순 정하기 - 타순은 dfs로 구현할 수 있도록 한다. - visit와 play 이용 - 4번째 선수는 항상 1번 2. 게임 진행 - 주어진 공식에 따라서 구현한다 dfs(1)로 시작해야하는데 dfs(0)으로 시작하여서 한참을 고민했다 dfs(0)으로 해도 visit[1]은 1이니깐 적용 안되고 그 다음부터 시작하니깐 보기에 있는 것은 다 맞았다 설계대로 되는지 검증하기 #include #include #include using namespace std; int visit[10]; int play[10]; int map[55][11]; int n; int house[5]; int a..

분류 dfs, 구현 요구사항 색종이를 최소로 이용하여 map에 있는 1을 다 가릴 수 있도록 하기 풀이 문제의 전체 흐름은 1. 현재 위치에서 붙일 수 있는 색종이 다 붙여보기 1.1. 붙이고 dfs로 이동 1.2 종료 후, 다시 복구하기 2. 다음 위치로 이동 3. 종료 조건 명시 하기 문제의 핵심은 현재에서 할 수 있는 행동을 모두 취한 뒤, 그 다음 위치로 이동하는 것이다. 현재 위치를 다시 한번 탐색할 경우, 탐색의 깊이가 깊어진다 #include #include using namespace std; int map[10][10]; int ansflag = 0; int ans = 987654321; int visit[6] = { 0,5,5,5,5,5 }; bool check(int r, int c,..

분류 분류, dfs 요구사항 적들이 0행~n-1행으로 이동할때, 궁수를 적절히 배치하여 처치할 수 있는 적들의 최대 수 구하기 풀이 전체적 문제의 흐름은 아래와 같다 1. dfs로 궁수 위치 정해주기 2. 적에서 궁수까지 거리 구하기 3. 제일 가까우면서 왼쪽에 있는 적 없애기 4. 적 이동 2~4번 반복 3번은 sort를 이용하여 처리하였다. 잡을 경우, map[r][c]가 1이면 0으로 바꾸어주고 cnt를 1증가 시켰다. #include #include #include #include #include #include using namespace std; struct go { int dist; int c; int r; }; int n, m, d; int map[17][17]; int visit[16];..