17142 번 : 연구소 3 백트래킹으로 활성화 할 바이러스의 조합을 만들었고, 이를 BFS 로 최소 시간을 구하는 방법으로 풀이했다. #include #include #include #include using namespace std; int N, M, cnt_0, ans; int dx[4] = { 0, 1, 0, -1 }; int dy[4] = { -1, 0, 1, 0 }; vector map; vector visited; vector virus, active; void bfs() { int y, x, time; queue q; int cnt_copy = cnt_0; if (cnt_0 == 0) { ans = 0; return; } visited.assign(N + 2, vector(N + 2, fa..
스터디
15685번 : 드래곤 커브 K 가 1 초과이니 경우, K 세대 드래곤 커브는 K-1 세대 드래곤 커브를 끝점을 기준으로 -90도 회전시킨 다음, 그것을 끝 점에 붙인 것이라고 한다. d 가 0~3 일 때, 각각 오른쪽, 위, 왼쪽, 아래인데 이것들을 90도 회전시키면 걸 d' 이라고 한다면 d' 은 위, 왼쪽, 아래, 오른쪽으로 d 를 기준으로 1, 2, 3, 0 이다. 따라서 -90도 회전시킨 d = (d' + 1) % 4 라는 걸 알 수 있다. prev_move 벡터에 이전 세대에 움직였던 방향들을 넣어두고, 역순으로 -90도 회전해서 적용하면 다음 세대 드래곤 커브가 된다. 정사각형의 경우 네 꼭짓점이 true 여도, 한 변이 비어있을 수 있어 고민했었는데, 문제를 다시 읽어보니 네 꼭짓저머이 드..
5430번 : AC 맨 앞자리를 간단하게 버리기 위해 deque 를 사용하여 해결했다. 1차 시도 때는 말 그대로 구현했고, 시간 초과가 나와서 그 다음으로는 R 이 연속으로 짝수 번 있으면 무시하고 넘어가도록 처리했다. 하지만 여전히 시간 초과가 나와서 고민해보니 R 명령의 경우 D 만 잘 처리해주면 마지막에 처리해도 상관 없는 것 같아서 Reverse 여부를 확인하는 isReverse 변수를 만들어서 처리했다. #include #include #include #include using namespace std; int T, n; bool isError, isReverse; string p, input, trans; deque seq; int main(void) { ios_base::sync_with_..
5567 번 : 결혼식 Queue 에 { 노드 번호, 1 번 노드와의 거리 } 를 넣어서 BFS 로 탐색하도록 구현했다. #include #include #include using namespace std; int n, m, a, b; vector relation; vector visited; int main(void) { int ans = 0; queue q; cin >> n >> m; relation.assign(n + 1, vector()); visited.assign(n + 1, false); for (int i = 0; i > a >> b; relation[a].push_back(b); relation[b].push_back(a); } q.push({ 1, 0 })..
16234 번 : 인구 이동 BFS 로 연합의 인구 수의 합을 구한 후, 칸의 개수로 나누어 평균 인구 수를 구했다. BFS 로 연결된 칸을 확인하며 A_union 에 위치를 저장한 뒤 평균 인구 수를 구한 후 A_union 내의 모든 값을 평균 인구 수로 대체했다. 이렇게 모든 칸이 조건을 충족하지 않을 때까지 반복하여 답을 구했다. #include #include #include using namespace std; int N, L, R; int dx[4] = { 0, 1, 0, -1 }; int dy[4] = { 1, 0, -1, 0 }; vector A; vector visited; queue A_union; int bfs(int x, int y) { int cnt = 1, total = 0; q..
