나만의 문제집 2 ( 쉽게, 깔끔하게, 시간복잡도가 좋게 )
카테고리: Algorithm
Chapter 01 자료구조 ( 중요도 상 )
Chapter 02 시뮬레이션 ( 중요도 상 )
02-1 아기 상어 ( 16236 )
- 설명
// https://donggoolosori.github.io/2020/10/08/boj-16236/
02-2 나무 재테크 ( 16235 )
- 설명
02-3 캐슬 디펜스 ( 17135 )
- 설명
02-4 게리맨더링 2 ( 17779 )
- 설명
02-5 마법사 상어와 토네이도 ( 20057 )
- 설명
02-6 마법사 상어와 파이어스톰 ( 20058 )
- 설명
02-7 사다리 조작 ( 15684 )
- 설명
02-8 주사위 굴리기 2 ( 23288 )
- 설명
02-9 원판 돌리기 ( 17822 )
- 설명
02-10 구슬 탈출 2 ( 13460 )
- 보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오
#include<iostream>
#include<string>
#include<queue>
using namespace std;
//얘가 큐에 넣는애
struct INFO
{
int rx, ry, bx, by, cnt;
};
INFO start;
string map[11];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int bfs()
{
int visit[10][10][10][10] = { 0 };
queue<INFO> q;
q.push(start);
visit[start.rx][start.ry][start.bx][start.by] = 1;
int ret = -1;
while (!q.empty())
{
INFO cur = q.front();
q.pop();
//종료조건
if (cur.cnt > 10)break; //10번이 넘었다면? 실패
if (map[cur.rx][cur.ry] == 'O' && map[cur.bx][cur.by] != 'O')
{
ret = cur.cnt; // //R만 탈출 했다면? 성공
break;
}
//어떤 애를 queue에 넣을 것인가?
for (int i = 0; i < 4; i++)
{
int next_rx = cur.rx;
int next_ry = cur.ry;
int next_bx = cur.bx;
int next_by = cur.by;
//빨간공이 벽에 닿을 때 까지 간다.
while (1)
{
if (map[next_rx][next_ry] != '#' && map[next_rx][next_ry] != 'O')
{
next_rx += dx[i]; next_ry += dy[i];
}
else
{
if (map[next_rx][next_ry] == '#')
{
next_rx -= dx[i]; next_ry -= dy[i];
}
break;
}
}
//파란공이 벽에 닿을 때 까지 간다.
while (1)
{
if (map[next_bx][next_by] != '#' && map[next_bx][next_by] != 'O')
{
next_bx += dx[i]; next_by += dy[i];
}
else
{
if (map[next_bx][next_by] == '#')
{
next_bx -= dx[i]; next_by -= dy[i];
}
break;
}
}
if (next_rx == next_bx && next_ry == next_by)
{
if (map[next_rx][next_ry] != 'O')
{
int red_dist = abs(next_ry - cur.ry) + abs(next_rx - cur.rx);
int blue_dist = abs(next_by - cur.by) + abs(next_bx - cur.bx);
if (red_dist > blue_dist)
{
next_rx -= dx[i]; next_ry -= dy[i];
}
else
{
next_bx -= dx[i]; next_by -= dy[i];
}
}
}
if (visit[next_rx][next_ry][next_bx][next_by] == 0)
{
visit[next_rx][next_ry][next_bx][next_by] = 1;
INFO next;
next.rx = next_rx;
next.ry = next_ry;
next.bx = next_bx;
next.by = next_by;
next.cnt = cur.cnt + 1;
q.push(next);
}
}
}
return ret;
}
int main()
{
int N, M;
cin >> N >> M;
for (int i = 0; i < N; i++)
{
cin >> map[i];
for (int j = 0; j < M; j++)
{
if (map[i][j] == 'R')
{
start.rx = i;
start.ry = j;
}
if (map[i][j] == 'B')
{
start.bx = i;
start.by = j;
}
}
}
start.cnt = 0;
int ans = bfs();
cout << ans;
return 0;
}
Chapter 03 그래프 ( 중요도 중 )
03-1 말이 되고픈 원숭이 ( 1600 )
- 설명
// 다익스트라 문제 4개, 참고로 다익스트라는 DP의 일종이다
// 플로이드 워셜 문제 3개
// 유니온 파인드 문제 3개
03-2 움직이는 미로 탈출 ( 16954 )
- 설명
03-3 벽 부수고 이동하기 ( 2206 )
- 설명
03-4 모양 만들기 ( 16932 )
- 설명
03-5 서울 지하철 2호선 ( 16947 )
- 설명
03-6 육각 보드 ( 12946 )
- 설명
03-7 모양 만들기 ( 16932 )
- 설명
03-8 텀 프로젝트 ( 9466 )
- 설명
03-9 산책 (small) ( 22868 )
- 설명
Chapter 04 DFS ( 중요도 하 )
04-1 문제
- 설명
Chapter 05 백트래킹 ( 중요도 하 )
05-1 문제
- 설명
Chapter 06 BFS ( 중요도 상 )
06-1 문제
- 설명
Chapter 07 완전탐색 ( 중요도 상 )
07-1 종이 조각 ( 14391 )
- 영선이가 얻을 수 있는 점수의 최댓값을 출력한다
// 강좌 - 코딩 테스트 준비 - 기초
#include <bits/stdc++.h>
using namespace std;
int rows, cols; // 행, 열 크기
int board[5][5]; // 지도
bool visited[5][5]; // 방문 여부
int answer; // 최대 합
void input()
{
cin >> rows >> cols; // 행, 열 크기 입력
string str;
for (int r = 0; r < rows; r++) // 지도 입력
{
cin >> str;
for (int c = 0; c < cols; c++)
{
board[r][c] = str[c] - '0'; // 문자를 숫자로 변환하여 지도에 저장
}
}
}
void dfs(int r, int c)
{
// 모든 행에 대한 숫자 조합이 결정된 경우
if (r == rows)
{
int sum = 0; // 숫자 조합의 합
// 각 행에 대해
for (int r = 0; r < rows; r++)
{
int temp = 0; // 현재 숫자 조합
// 각 열에 대해
for (int c = 0; c < cols; c++)
{
// 방문한 열의 숫자를 숫자 조합에 추가
if (visited[r][c])
temp = temp * 10 + board[r][c];
// 방문하지 않은 열을 만난 경우
else
{
sum += temp; // 숫자 조합의 합에 현재 숫자 조합을 더함
temp = 0; // 새로운 숫자 조합을 만들기 위해 0으로 초기화
}
}
sum += temp; // 마지막 숫자 조합을 합에 더함
}
// 각 열에 대해
for (int c = 0; c < cols; c++)
{
int temp = 0; // 현재 숫자 조합
// 각 행에 대해
for (int r = 0; r < rows; r++)
{
// 방문하지 않은 행의 숫자를 숫자 조합에 추가
if (!visited[r][c])
temp = temp * 10 + board[r][c];
// 방문한 행을 만난 경우
else
{
sum += temp; // 숫자 조합의 합에 현재 숫자 조합을 더함
temp = 0; // 새로운 숫자 조합을 만들기 위해 0으로 초기화
}
}
sum += temp; // 마지막 숫자 조합을 합에 더함
}
answer = max(answer, sum); // 최대 합을 업데이트
return;
}
// 한 행에 대한 모든 열에 대한 숫자 조합이 결정된 경우
if (c == cols)
{
dfs(r + 1, 0); // 다음 행을 탐색
return;
}
// 현재 열의 숫자를 방문한 경우
visited[r][c] = true;
dfs(r, c + 1); // 다음 열을 탐색
// 현재 열의 숫자를 방문하지 않은 경우
visited[r][c] = false;
dfs(r, c + 1);
}
void solve()
{
dfs(0, 0);
cout << answer << "\n";
}
int main()
{
input();
solve();
return 0;
}
// 강좌 - 코딩 테스트 준비 - 기초
// https://imnotabear.tistory.com/272 참고
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
// 4 x 4 배열과 각 칸을 방문했는지 체크하는 배열
int arr[4][4];
bool check[4][4] = { false };
int row, col, result = 0; // 행, 열, 최대 합
void brute(int num, int sum)
{
int x = num % col; // 현재 칸의 열 좌표
int y = num / col; // 현재 칸의 행 좌표
if (row * col <= num) // 모든 칸을 다 돌았으면
{
result = max(result, sum); // 최대 합 갱신
return;
}
if (check[y][x]) brute(num + 1, sum); // 이미 방문한 칸이면 다음 칸으로
else // 방문하지 않은 칸이면
{
int val, ny, nx;
val = arr[y][x]; // 현재 칸의 값을 숫자로 만들기 위한 변수 초기화
check[y][x] = true; // 현재 칸 방문 체크
brute(num + 1, sum + val); // 다음 칸으로 이동하면서 합에 현재 칸의 값 더하기
check[y][x] = false; // 다음 경우를 위해 방문 체크 취소
// 아래쪽으로 뻗어나가는 경우
for (int k = 1; k < row - y; k++)
{
nx = x;
ny = y + k;
val = val * 10; // 자릿수를 늘려서 숫자 만들기
val = val + arr[ny][nx]; // 새로운 칸의 값을 더해서 숫자 만들기
for (int j = 1; j <= k; j++) // 지금까지 뻗어나간 칸들 방문 체크
check[y + j][nx] = true;
brute(num + 1, sum + val); // 다음 칸으로 이동하면서 합에 숫자 더하기
for (int j = 1; j <= k; j++) // 다시 방문 체크 취소
check[y + j][nx] = false;
}
val = arr[y][x]; // 다시 변수 초기화
// 오른쪽으로 뻗어나가는 경우
for (int k = 1; k < col - x; k++)
{
ny = y;
nx = x + k;
if (check[ny][nx]) return; // 이미 방문한 칸이면 경우의 수 끝내기
val = val * 10;
val = val + arr[ny][nx];
for (int j = 1; j <= k; j++)
check[ny][x + j] = true;
brute(num + 1, sum + val);
for (int j = 1; j <= k; j++)
check[ny][x + j] = false;
}
}
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> row >> col;
string str;
for (int i = 0; i < row; i++)
{
cin >> str;
for (int j = 0; j < col; j++)
arr[i][j] = str[j] - '0';
}
brute(0, 0);
cout << result;
return 0;
}
07-2 NxM 보드 완주하기 ( 9944 )
- 보드의 상태가 주어졌을 때, 모든 칸을 방문하기 위한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오
// 강좌 - 알고리즘 중급 - 2/3
// https://www.acmicpc.net/problem/9944
07-3 Baaaaaaaaaduk2 (Easy) ( 16988 )
- 첫째 줄에 현재 판에서 돌 2개를 두어 죽일 수 있는 상대 돌의 최대 갯수를 출력한다
// 강좌 - 알고리즘 중급 - 2/3
// https://www.acmicpc.net/problem/16988
07-4 사다리 조작 ( 15684 )
- i번 세로선의 결과가 i번이 나오도록 사다리 게임을 조작하려면, 추가해야 하는 가로선 개수의 최솟값을 출력한다. 만약, 정답이 3보다 큰 값이면 -1을 출력한다. 또, 불가능한 경우에도 -1을 출력한다
// 강좌 - 알고리즘 중급 - 2/3
// https://www.acmicpc.net/problem/15684
07-5 스티커 붙이기 ( 18808 )
- 설명
// 강좌 - 없음
// https://www.acmicpc.net/problem/18808
07-6 색종이 붙이기 ( 17136 )
- 설명
// 강좌 - 코딩 테스트 준비 - 문제
// https://www.acmicpc.net/problem/17136
07-7 2048 ( 12100 )
- 설명
// 강좌 - 코딩 테스트 준비 - 연습
// https://www.acmicpc.net/problem/12100
07-8 다리 만들기 2 ( 17472 )
- 설명
// 강좌 - 코딩 테스트 준비 - 문제
// https://www.acmicpc.net/problem/17472
07-9 스도미노쿠 ( 4574 )
- 설명
// 강좌 - 코딩 테스트 준비 - 연습
// https://www.acmicpc.net/problem/4574
Chapter 08 슬라이딩윈도우 + 투포인터 ( 중요도 상 )
Chapter 09 문자열 ( 중요도 중 )
Chapter 10 DP ( 중요도 하 )
10-1 자물쇠 ( 1514 )
- 첫째 줄에 최소 몇 번을 돌려야 풀 수 있는지 구하는 프로그램을 작성하시오
// https://www.acmicpc.net/problem/1514
댓글남기기