ans 가 지금까지 구한 개수(cnt) 보다 크면 종료 (BackTracking)1 |
|
step 변수를 두어 범위를 좁혀간다.가까운 적을 먼저 찾아 공격하기 위해 BFS 탐색을 사용한다.
queue 를 만들어 자신의 위치를 저장하고 탐색 시작 (최대 D까지)check array를 사용해 공격한 적일 경우 해당 step + 1의 값을 준다. (step이 0부터 시작, check는 0으로 초기화 되어있기에)step을 이용해 check에 값을 준 이유는 다음 step에서 궁수의 위치가 이동될 때 이전 턴에서 공격 당해 제외된 적인지 아닌지를 판단하기 위함이다. (step의 값이 변하니까 중복되지 않게 탐색 가능)1 |
|
1 |
|
Goal: (0, 0) 과 (0, 1)에 위치한 하나의 파이프를 (N, N)으로 옮기는 방법의 개수
불가능한 경우 0
오른쪽, 아래, 오른쪽 아래 대각선 방향으로 옮길 수 있음
옮길 때 45도 회전 가능
벽에 닿으면 안됨
입력
N: 3~16
빈칸 0 벽은 1
// 예제
0 0 1 0
0 0 0 0
0 0 0 0
0 0 0 0
-> 0
맨 처음 파이프는 (0,0), (0,1) 즉 가로이기에 가능한 방향인
오른쪽, 오른쪽 아래 대각선으로 옮길 수 없다.
check1 | 가로: 오른쪽 1칸 검사 |
위를 이용하여 탐색 코드를 구현한다.1
2
3
4
5
6
7
8void 탐색(현재 위치, 현재 타입)
도착했을 때 answer++후 리턴
for(3번)
check할 위치(오른쪽, 아래, 오른쪽 아래)
경계확인
(벽이 아니고 자신과 같은 type)이거나(벽이 아니고 대각선)
탐색(옮길 위치, 가능한 타입)
모든 곳을 검사했을 때만 대각선 탐색
1 |
|
Stack을 사용하여 연산자만 넣는다.Stack이 비어있지 않으면 꺼내어 연산자에 맞게 계산한다.*(곱셈)은 괄호가 필요 없을 것이라 생각하여 괄호를 넣어주지 않았다.
하지만 연산은 왼쪽에서부터 순서대로 진행되기에 곱셈도 괄호가 필요하다.
1 |
|
ans(정답)의 초기값을 0으로 설정해서 틀렸다. 정답은 (-2^31, 2^31)의 범위에 속한다.
1 |
|
1 |
|
Goal: 종료되는 시간은?
입력
0: 빈 칸
1~6: 물고기 크기
9: 아기 상어
입력값 다루기
struct shark {
int r, c, size, cnt= 0;
}baby;
아기 상어의 위치, 크기, 먹은 수를 저장할 수 있도록 구조체를 만든다.
part_time)part_time)을 더해준다.1 | void findPrey(int row, int col) { |
isEnd는 true가 되므로 작업이 종료된다.1 | void selectPrey(queue<pair<int, int>> &prey) { |
먹을 물고기가 선택되면 아기 상어의 위치를 변경해준다. 크기 또한 먹은 수에 맞게 변경해준다.
1 |
|
while (!q.empty()) q.pop(); 라인 때문에 시간초과가 걸린 것 같아 굳이 이럴 필요 없이 먹을 수 있는 물고기가 있다면 selectPrey() 를 호출하여 물고기를 선택하고 시간을 갱신해준 후 return하도록 하였다. 이러면 다시 findPrey() 를 호출하기에 업데이트 된 아기 상어 위치가 queue에 들어가고 작업을 수행한다. q를 비울 필요가 없어짐.1 |
|
1 |
|
처음에 3차원 벡터로 해당 칸에 나무 정보를 저장하였지만 계절마다 작업을 수행할 때 상당히 비효율적이라 시간초과가 떴다.
→ 문제의 조건을 잘 보면 답이 보인다. (항상 느끼는 거지만 어떤 자료구조를 선택할지가 중요)
위 조건을 도합하면 deque 가 가장 적합하다. deque<int> tree[10][10]
나이가 어린 나무가 앞에 즉, 오름차순으로 정렬되어 있어야 하는데, 처음에 각 칸에 하나씩 입력 받고 추가될 때 앞부분에 나무를 추가해주면 되기 때문이다. 죽는건 앞에서부터 탐색을 하다가 죽는 나무가 생기면 그 뒤부터 이미 죽은 나무가 되기에 죽을 나무 개수만 카운트하고 뒤에서부터 개수만큼 pop하면 되기 때문이다.
1 |
|
1 |
|
N x N 크기의 배열을 전부 탐색하면서 check표시가 되어있지 않은 부분은 인구 이동이 가능한지 확인 작업이 수행된다.
작업 동안 누적 합과 연합에 포함된 나라 수를 계산해야 한다.
위 작업이 끝나면 이제 따로 저장한 누적합과 사람 수를 이용해 N x N 크기의 배열을 바꿔준다. (실질적 인구 이동)
만약 flag가 false 즉, 인구이동이 없다면 종료한다.
BFS보다 훨씬 빠르고 깔끔하며 명료하다. 처음에 BFS로 할 생각을 했던 것은 N x N 크기의 배열 값을 미리 바꾸면 인구 이동에 영향을 미치게 된다는 생각에 코드를 작성했었는데 생각해보니 한 번 탐색이 끝나면(BFS든 DFS든) check 표시 되어 있기에 영향을 주지 않고 한 번 탐색할 때 위치만 미리 벡터에 저장해주면 된다.
1 |
|
1 |
|
Goal: 치킨집 중에서 최대 M개를 골랐을 때 도시의 치킨 거리 최솟값
해당 집을 고르면 배열에 넣고 아니면 넣지 않음1
2
3
4
5
6
7
8
9
10
11void combination(int idx) {
if (select_idx == m) {
BFS 이용하여 치킨 거리 구하기
return;
}
if (idx == total_chicken) return;
combination(idx + 1); // 선택하지 않기
select[select_idx++] = idx;
combination(idx + 1); // 선택하기
select_idx--; // 다른 경우의 수를 위해 인덱스 빼주기 (중요)
}
중요라고 되어있는 부분을 작성하지 않으면 모든 경우의 수를 구할 수 없다. 경우의 수가 꼬여버림.
4개 중에 2개를 고른다고 하면1
2
3
4
5
6
7
8comb(0)
comb(1)
comb(2)
comb(3)
...
이런식으로 호출이 이루어지기에 (3, 2) 경우가 먼저 완성된다.
완성되고 BFS이용하여 치킨 거리 구하고 return되면 select_idx를 빼준다.
그럼 2자리에 다른 경우가 넣어질 수 있다. (3, 1)
BFS를 이용하여 한 칸씩 갈 때 1초 증가
그러다 1을 만나면 해당 초를 더 해준다.
BFS를 이용하면 동시에 1을 만나기에 time만 더해주어서는 안된다.
동시에 발견한 집의 수만큼 time을 더해주어야 한다.
모든 1을 만났으면 종료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
30void bfs() {
int time = 0, house = 0, dist = 0;
memset(check, 0, sizeof(check));
queue<pair<int, int>> q;
for (int i = 0; i < select_idx; ++i) {
q.push({ chicken[select[i]].r, chicken[select[i]].c });
while (!q.empty()) {
time++;
int cnt = 0;
int len = q.size();
for (int i = 0; i < len; ++i) {
int r = q.front().first;
int c = q.front().second;
q.pop();
check[r][c] = true;
for (int i = 0; i < 4; ++i) {
int x = r + dx[i];
int y = c + dy[i];
if (isBound(x, y) && !check[x][y]) {
check[x][y] = true;
if (city[x][y] == 1) {
house++; cnt++;
}
q.push({ x, y });
}
}
}
dist += time * cnt; // 해당 초에 만난 집의 수 만큼 이동거리 더해주기
}
}
이 중 가장 최소인 치킨 거리 구하기
1 | dist += time * cnt; // 해당 초에 만난 집의 수 만큼 이동거리 더해주기 |
컴파일 에러 (index라는 변수명은 기피하자…) select_idx로 변경
1 |
|
1 |
|
입력
드래곤 커브 개수 N (~20)
x, y (드래곤 커브 시작 점) ~100
d (시작 방향)
g (세대) ~10
드래곤 커브는 서로 겹칠 수 있다.
Goal: 만들어진 드래곤 커브에서 정사각형 4개의 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 구하기 (모양이 정사각형이 아니어도 4개의 꼭짓점만 만족하면 된다.)
아래 그림 참고.
끝점에서 이동을 수행하니 위치 좌표는 끝점만 알면된다.
1 | // input : 3 3 0 1 |
2세대 설명: 1세대에서 방향이 [0, 1]로 저장되어 있다. 끝점부터 시작하기에 방향 1이 시계방향으로 90도 회전하면 방향 2가 된다. [0, 1, 2]
이후 0이 시계방향으로 90도 회전하면 방향 1이된다. [0, 1, 2, 1]
드래곤 커브 위의 규칙대로 그리기
0세대 까지 그려놓고 (0세대가 아니라면) 1세대부터 그린다.
direction 배열에 위의 [0, 1, 2, 1]과 같은 값이 들어간다.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18int clockwise[4] = { 1, 2, 3, 0 };
void draw(int x, int y, int d, int g) {
int idx = 0;
check[y][x] = true;
direction[idx++] = d;
while(g--) {
int len = idx;
for (int i = len-1; i >= 0; --i) {
d = clockwise[direction[i]];
x += dx[d];
y += dy[d];
if (x > -1 && y > -1 && x < MAX && y < MAX) {
check[y][x] = true;
}
direction[idx++] = d;
}
}
}
배열은 최대 100 x 100의 크기를 가지기에 0~99까지 check 값이 존재할 수 있다. (사실상 98까지만 확인하면 된다.)
1 1 (0, 0)을 기준으로 오른쪽, 아래, 오른쪽 아래 대각선만 확인하면 된다.
1 1
1 |
|
조합을 구하기 전에 입력값이 어떻게 들어오나 확인해보자.
a b가 입력되면 a행에 b열 사다리와 b+1열 사다리가 연결된다.
이를 array[a][b] = 1(사다리 있음)으로 표시하면 b+1로 갈 수 있다는 뜻이다.
반대로 b+1지점에서 array[a][b]값이 1인걸 확인하면 b로 갈 수 있다는 뜻이다.
이를 활용하여 조합을 구해보자.
모든 행의 1열부터 N-1열까지 탐색해야 한다.
단, 현재 위치뿐만 아니라 자신의 왼쪽, 오른쪽도 확인해야 한다. (연속으로 설치하지 못하기 때문)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
161행 1열 선택 시 다음 가능한 경우 (N에 표시하는 것은 의미 X - 입력값 생각)
1행 - 1(x), 2(x), 3 ... N-1
2행 - 1, 2, 3 ... N-1
...
H행 - 1, 2, 3 ... N-1
for (int i = idx; i <= H; ++i) {
for (int j = 1; j < N; ++j) {
if (visit[i][j]) continue; // 현재 확인
if (j > 1 && visit[i][j - 1]) continue; // 왼쪽 확인
if (visit[i][j + 1]) continue; // 오른쪽 확인
visit[i][j] = true; // 선택 표시
selectAll(i, cnt + 1); // 다음 선택
visit[i][j] = false;
}
}
1 |
|