정화 코딩

https://www.acmicpc.net/problem/17370 각 이동은 위와 같이 벡터로 표현할 수 있다. 실수 좌표계에서 방문 처리를 하는 법은 여러 방법이 있을 수 있겠지만 나는 두가지 방법으로 구현해보았다. 1. 실수 좌표를 그대로 사용, 대신 오차 범위를 두고 비교벡터는 동일하게 (1, 0) (0.5, sqrt(3)/2), (-0.5, sqrt(3)/2), ... 이런 식으로 계산한다. 다만 소수점 둘째자리 정도까지 반올림해주었다. 그래야 계산 상의 차이로 아주 작은 오차가 생겼을 때 같은 점으로 인식할 수 있다. 나는 실수를 scale 후에 반올림을 해서 정수로 만들고, pair을 원소로 하는 set으로 방문 처리를 해주었다. #include #include #include #inclu..

https://www.acmicpc.net/problem/15686 일단 모든 집과 모든 치킨집의 쌍에 대해서 거리를 구하기 위해서 집의 개수만큼 bfs를 돌렸다. (근데 생각해보니 bfs 쓸 필요 없이 좌표만 빼서 거리를 구할 수 있다.)그 결과(모든 집과 모든 치킨집의 쌍에 대한 거리)를 sp 배열에 담아두었다.그 후, 백트래킹으로 가능한 모든 치킨집 조합에 대해서 도시의 치킨 거리를 계산한다. 그 중 가장 최소인 값을 출력하면 된다. #include #include #include using namespace std;int dx[] = {1, -1, 0, 0};int dy[] = {0, 0, 1, -1};int n, m, hn, cn;int ans = 1000000;vector cchk;vector..

https://www.acmicpc.net/problem/23817 이 문제 풀 때 고수들이 옆에 있었어서 그들이 걍 다 해줌. 저는 풀이를 듣고 음 그렇구나. 천재다. 구현해볼게. 했음다. 첫번째 풀이. vst 배열: 현재 위치 (i, j) + 어느어느식당 방문했는지 (길이가 20인 비트스트링) 길이가 20인 비트스트링 → 2^20 하면 너무 큼 → 근데 어차피 최대가 5개 켜지는 거임 → 2^20 중에 안 쓰는 게 너무 많음 (어떤 걸 안 쓰는지 모름) → map 이용 vector>> → 최단 거리를 두번째 int에 저장하는 셈 vector>> (= vector>>) → 방문 했는지 안 했는지를 bool에 저장하는 셈 근데 이렇게 하면 터짐...  두번째 풀이.모든 식당과 식당 (+시작점) 사이의 거..

https://www.acmicpc.net/problem/1987 #include #include using namespace std;int r, c;vector m;bool vst[26];int maxc = 0;int di[] = {1, -1, 0, 0};int dj[] = {0, 0, 1, -1};void dfs(int curi, int curj, int cnt) { if (cnt > maxc) maxc = cnt; for (int k = 0; k = 0 && nxti = 0 && nxtj > r >> c; m = vector(r); for (int i = 0; i > m[i]; } vst[m[0][0] - 'A'] = true; dfs(0, 0, 1); ..

https://www.acmicpc.net/problem/2239 #include #include using namespace std;vector> s;vector> emp;int n;bool fin = false;bool chk(int idxi, int idxj, int num) { for (int i = 0; i >(9, vector(9)); emp = vector>(); for (int i = 0; i > str; for (int j = 0; j 스도쿠 판을 왼쪽 위부터 차례대로 읽어가며 빈칸에 1부터 9까지의 수를 넣어가면서 가능한 경우를 만나는 즉시 종료하고 출력하도록 했다. 백트래킹 문제이고, 탐색하는 함수 dfs와 가능한 경우인지 체크하는 함수 chk를 만들었다...

https://www.acmicpc.net/problem/19699 #include #include #include #include using namespace std;bool p[10000];int n, m;vector h;vector chk;set ans;void dfs(int idx, int res) { if (idx == m) { if (res > n >> m; h = vector(n); chk = vector(n, false); for (int i = 0; i > h[i]; sort(h.begin(), h.end()); dfs(0, 0); if (ans.empty()) { cout 우선 에라토스테네스 체로 1부터 10000까지 범위에..

05-1. 깊이 우선 탐색 023. 연결 요소의 개수 (백준 11724번) https://www.acmicpc.net/problem/11724 from sys import stdin import sys sys.setrecursionlimit(10000) n, m = map(int, stdin.readline().split()) data = [[] for i in range(n)] visited = [False] * n def DFS(v): visited[v] = True for i in data[v]: if not visited[i-1]: DFS(i-1) for i in range(m): a, b = map(int, stdin.readline().split()) data[a-1].append(b) dat..