정화 코딩

https://www.acmicpc.net/problem/17070 그냥 bfs 해주되, 파이프가 놓여 있는 방향까지 큐에 넣도록 했다. 그래서 현 상태를 기준으로 어떻게 움직일 수 있는지를 체크해서 (n, n)에 도달하면 한번 카운트 해주는 식으로 구혔했다.어차피 움직이는 방향이 무조건 오른쪽 또는 아래이기 때문에 시간 안에 해결 가능하다고 생각했는데, 제출해보니 좀 간당간당하고 dp로 풀어야 했던 문제인 듯하다. #include #include #include using namespace std;// 파이프가 놓여 있는 방향 {가로, 세로, 대각선}int px[] = {0, -1, -1};int py[] = {-1, 0, -1};vector>> d = { {{0, 1, 0}, {1, 1, 2}..

https://www.acmicpc.net/problem/14938 우선 모든 노드와 노드 사이의 최단 경로를 구해 놓는다.그 후 각 지역에 떨어졌다고 가정했을 때, 얻을 수 있는 아이템의 수를 구해서 최댓값을 찾는다. 모든 노드 간의 최단 경로가 필요하기 때문에 플로이드-워셜을 사용하였다. #include #include using namespace std;int MAX_SIZE = 1000000000;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m, r; cin >> n >> m >> r; vector item(n + 1); for (int i = 1; i > item[i];..

https://www.acmicpc.net/problem/14502 #include #include #include using namespace std;int n, m, ans;vector> a;int dx[] = {1, -1, 0, 0};int dy[] = {0, 0, 1, -1};int bfs() { queue> q; vector> vst(n, vector(m, 0)); for (int i = 0; i = 0 && nxti = 0 && nxtj > n >> m; a = vector>(n, vector(m)); for (int i = 0; i > a[i][j]; } } dfs(0, 0, -1); cout 백트래킹으로 3개의 벽을 놓는 모든 경우를 ..

https://www.acmicpc.net/problem/16236 #include #include #include #include using namespace std;int n, curs, cnt, time;vector> m;int dx[] = {1, -1, 0, 0};int dy[] = {0, 0, 1, -1};vector targetf(int si, int sj) { vector> vst(n, vector(n, -1)); queue> q; vector> fish; q.emplace(si, sj); vst[si][sj] = 0; while (!q.empty()) { int curi = q.front().first; int curj = q.fro..

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/12851 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, k; cin >> n >> k; int maxs = 100001; vector vst = vector(maxs, false); int timea = 0; int cnt = 0; queue> q; q.emplace(n, 0); vst[n] = true; while (!q.empty()) { int cur = q.front().first; int t..

https://www.acmicpc.net/problem/11779 #include #include #include using namespace std;int MAX_SIZE = 1000000000;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector>> g(n + 1); vector dst(n + 1, MAX_SIZE); vector route(n + 1); for (int i = 0; i > a >> b >> c; g[a].emplace_back(b, c); } int s, e; cin >> s >> ..

8회차 - BFS, DFS DFS와 BFShttps://www.acmicpc.net/problem/1260DFS, BFS 기본 문제입니다. 각 방식을 구현하고 방문하는 노드를 출력하면 됩니다.주의할 점 1. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 택해야 한다는 것입니다. 따라서 저는 입력을 받은 후 각 정점에 연결된 정점들에 대해 정렬을 한 번씩 진행해주었습니다.주의할 점 2. 탐색 여부 배열을 공유한다면 초기화가 필요합니다.#include #include #include #include using namespace std;vector vst;vector> g;void dfs(int cur) { vst[cur] = true; cout q; q.push(..