Seongkyun Han's blog
191006 백준 알고리즘 문제풀기
06 Oct 2019 | baekjoon[14890번] 경사로
- 난이도: 상
- 전형적인 시뮬레이션 문제로, 푸는데 2시간정도 소요됐다. 시험에 나왔으면 틀렸다.
- 문제 풀이 떠올리는데 1시간, 구현에 1시간..
- 구현은 정말 쉬웠지만, 풀이를 나누고 case 분류하는데 정말 애를 많이 먹엇다.
- 시뮬레이션 문제의 경우, 한 번에 모두 해결하려면 정말 답도 없다.
- 문제를 작게 쪼개고, case를 잘 분류해서 하나하나 해결해가야 풀 수 있을 것 같다.
- 처음에 문제를 보자마자 쉽겠지 하고 무턱 시작했다가 큰 낭패를 봤다.
- 시뮬레이션 문제를 풀 때는
- 우선, 문제를 작게 나누고(가능한 상황으로)
- 나눠진 문제에 대해 조건을 확인하고
- 알고리즘으로 구현해야 한다.
- 전형적인 시뮬레이션 문제로, 푸는데 2시간정도 소요됐다. 시험에 나왔으면 틀렸다.
- 문제
- https://www.acmicpc.net/problem/14890
- NxN 맵과 경사로 길이가 주어질 때, 경사로를 두고 해당 맵을 가로, 세로로 건널 수 있는 경우의 수를 출력한다.
- 하나의 알고리즘으로 두 개의 회전된 맵을 만들고, 이를 이용해 풀면 된다.
- 풀이
- 우선, 한 줄의 가로 배열에 대한 풀이만 해결하면 문제를 풀 수 있다.
- 이를 세로로 쌓고, 가로로 돌려서 적용하는 식으로 전체에 가로/세로 방향의 경우의 수를 모두 따질 수 있음
- case 분류
- 다음 칸과 높이가 같은 경우
- 다음 칸이 높고, 1 차이나는 경우
- 다음 칸이 낮고, 1 차이나는 경우
- 외의 경우는 무조건 건널 수 없다(break)
- 시뮬레이션 문제에서 제일 중요한건 case를 분류하는것이다!
- 분류된 case를 토대로 조건에 맞게 완성시켜 나가면 되기 때문
- 우선, 한 줄의 가로 배열에 대한 풀이만 해결하면 문제를 풀 수 있다.
#pragma warning(disable:4996)
#include <iostream>
#include <queue>
#include <tuple>
#include <cmath>
#include <algorithm>
using namespace std;
int map_a[100][100]; // 가로 맵 저장용
int map_b[100][100]; // 세로 맵 저장용
bool flat(int arr[], int s, int d) // 인덱스 s부터 d까지 평평한가(그래야 경사로를 둘 수 잇음)
{ // s: start index, d: dest index
int cnt = 0;
for (int i = s; i < d; i++)
{
if (arr[i] - arr[i + 1] != 0)
{
cnt++;
}
}
if (cnt == 0)
return true; // 평평하면 true 반환
else
return false; // 아니면 false 반환
}
bool stair(int arr[], int s, int d) // s부터 d까지 계단 세울 수 있는가 (계단이 존재하지 않아야 함)
{
int cnt = 0;
for (int i = s; i <= d; i++)
{
if (arr[i] == 2)
cnt++;
}
if (cnt == 0)
return true;
else
return false;
}
void make_stair(int check[], int s, int d) // 계단을 세운다.
{
for (int i = s; i <= d; i++)
{
check[i] = 2;
}
}
bool checker(int arr[], int w, int l)
{
int check[100]; // check 배열엔 지나간 경우는 1, 경사로 세운 경우는 2, 못 지나간 경우는 0으로 표시
std::fill_n(check, w, 0); // check배열 0으로 초기화
for (int i = 0; i < w; i++)
{ // 전체 배열에 대해서
if (i == w - 1)
{ // 마지막 인덱스까지 왔다면 앞 인덱스의 조건은 모두 통과한 경우다.
check[i] = 1; // 따라서 1로 채운다.
break;
}
if (arr[i] == arr[i + 1])
{//다음칸과 높이가 같은 경우
if (check[i] == 0) // 만약 현재 위치에 경사로가 존재하지 않는다면
check[i] = 1; // 지나간다.
else
continue; // 경사로가 존재한다면 넘어간다.(경사로 중복 방지)
}
else if (arr[i] < arr[i + 1] && arr[i + 1] - arr[i] == 1)
{//다음칸이 높고 1 차이나는 경우
int sx = i - l + 1; // 경사로 처음 좌표
int dx = i; // 경사로 마지막 좌표
if (0 <= sx && flat(arr, sx, dx) && stair(check, sx, dx))
{//이전에 길이가 충분하고, 경사로 구간이 평평하며, 경사로 구간에 다른 경사로가 존재하지 않다면
make_stair(check, sx, dx);//해당 구간 경사로를 만든다.
}
else break; // 아니라면 break(뒤 쪽 볼 필요 없음)
}
else if (arr[i] > arr[i + 1] && arr[i] - arr[i + 1] == 1)
{//다음칸이 낮고 1 차이나는 경우
int sx = i;
int dx = i + l;
if (dx < w && flat(arr, sx + 1, dx) && stair(check, sx + 1, dx))
{//다음에 경사로를 둘 길이가 충분하고, 경사로 구간이 평평하며, 경사로 구간에 다른 경사로가 존재하지 않다면
check[i] = 1; // 현재 위치를 1로 초기화(지나갔으므로)
make_stair(check, sx + 1, dx); // 경사로를 둔다.
i = dx - 1; // index를 경사로 마지막 위치로 초기화한다.(중복으로 for문 돌을 필요 없음)
}
else break; // 아니라면 break(뒤쪽 볼 필요 없음)
}
else // 아닌 경우 무조건 갈 수 없음
break;
}
//갈 수 있는지 check
bool go = true;
for (int i = 0; i < w; i++)
{
if (check[i] == 0)
go = false; // 만약 끝까지 못간경우 false반환
}
return go;
}
int main()
{
int N, L;
scanf("%d %d", &N, &L);
for (int j = 0; j < N; j++)
{
for (int i = 0; i < N; i++)
{
scanf("%d", &map_a[j][i]); // 가로 방향 입력
map_b[i][j] = map_a[j][i]; // 세로 방향 초기화
}
}
int ans = 0;
for (int j = 0; j < N; j++)
{
ans += checker(map_a[j], N, L); // 가로 방향 계산
}
for (int j = 0; j < N; j++)
{
ans += checker(map_b[j], N, L); // 세로 방향 계산
}
printf("%d\n", ans);
//system("pause");
return 0;
}
[15685] 드래곤 커브
- 난이도: 중
- 시뮬레이션 문제로, 풀이를 떠올리는데는 30분도 걸리지 않았지만 구현하면서 부딫히는 문제들, 그리고 조건들을 고려하느라 총 2시간 정도 소요.
- 문제 자체를 이해하는데 많은 시간이 소요되었다.
- 문제를 나누고, 구현했으며, 문제를 나누는 과정 및 풀이를 떠올리는 과정에서 만약 잘못된 길로 빠지면 답도 없다.
- 특히 시뮬레이션문제는 더욱 더 그런듯 하다.
- 다시한번 느끼지만, 시뮬레이션 문제는
- 문제를 정확하게 이해하고
- 모든 조건을 정확하게 파악하고
- 문제를 제대로 쪼개는 것
- 위 세가지가 가장 중요한 듯 하다.
- 문제
- https://www.acmicpc.net/problem/15685
- x, y, d, g 순으로 주어지는 드래곤 커브가 있다.
- x, y는 시작점 좌표, d는 방향, g는 몇 번 회전하면서 이어갈지를 의미한다.
- d는 0, 1, 2, 3 순으로 오른쪽, 위, 왼쪽, 아래로 매핑된다.
- g 동안 이어붙여지며 맵이 늘어난다.
- 전체 맵의 크기는 100x100 이다.
- 풀이
- 문제를 나누면 아래와 같다.
- 우선 시작 선을 긋는다.
- 처음 포인트와 방향에 대한 선분을 긋는다.
- 시작 섬을 기준으로 끝점을 정의한다.
- 끝 점을 기준으로 맵이 회전하게 되며
- 시작점을 기준으로 회전된 맵이 와서 붙는다.
- 맵을 회전시킨다.
- g 동안 회전시키며 위의 규칙들을 따른다.
- 완성된 맵 상의 네모칸 갯수를 따진다.
- 우선 시작 선을 긋는다.
- 문제를 나누면 아래와 같다.
- 주의
memset(array, number, sizeof(array))는 1차원 배열에서도 사용 가능하지만 2차원에서도 가능하다.- 사용 시 반드시
#include <cstring>을 추가한다!(안그러면 런타임 에러 뜸) - 앞으로는 그때그때 include하는 헤더를 따로 따로 지우고 필요에 따라 불러쓰는 연습을 해야겟다.
- 인덱스는 큰 차이가 없다면 1칸정도 넉넉히 잡는게 좋은듯 하다.
- 본 문제에서도 100 딱 맞춰 했는데 알고보니 101까지 선언해야 문제 조건을 만족한다.
#pragma warning(disable:4996)
#include <iostream>
#include <queue>
#include <tuple>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
int map[101][101]; // 맵 저장용
int check[101][101]; // 맵 중간 계산용 (동일 좌표 내에서)
int temp[101][101]; // 맵 중간 계산용 (회전시)
int dx[] = { 1,0,-1,0 }; // 각각 0, 1, 2, 3에 대한 이동 매핑
int dy[] = { 0,-1,0,1 };
int answer = 0; // 정답
vector<tuple<int, int, int, int>> dots; // x, y, d, g 저장용
void rotate(int &sx, int &sy, int &cx, int &cy, int N); // 회전 함수
void calc_map(int n); // 점수 계산 함수
void make_map(int n)
{
for (int i = 0; i < dots.size(); i++)
{ // 각 x, y, d, g 좌표에 대해
memset(check, 0, sizeof(check)); // check 배열 초기화
memset(temp, 0, sizeof(check)); // temp 배열 초기화
int sx, sy, d, g;
tie(sx, sy, d, g) = dots[i]; // x, y, d, g 저장
map[sy][sx] = 1; // 최종 저장 맵용 시작좌표 check
check[sy][sx] = 1; // 이번 turn 계산용 시작좌표 check
int nx, ny;
nx = sx + dx[d]; // 마지막 좌표 저장
ny = sy + dy[d];
if (0 <= nx && nx < n && 0 <= ny && ny < n)
{ // 마지막 좌표가 범위를 벗어나지 않는다면
map[ny][nx] = 1; // 최종 저장 맵용 check
check[ny][nx] = 1; // 이번 turn 계산용 check
while (g--)
{ // 회전 횟수만큼 회전
rotate(sx, sy, nx, ny, n); // 회전
} // 위 함수에서 while 문 내의 nx, ny가 초기화됨.(회전중심점)
}
else continue;
}
}
void calc_map(int n)
{
int sum = 0;
for (int j = 0; j < n - 1; j++)
{
for (int i = 0; i < n - 1; i++)
{
sum = 0;
for (int y = 0; y < 2; y++)
{
for (int x = 0; x < 2; x++)
{
if (map[j + y][i + x] > 0)
{
sum++; // 해당 좌표에 값이 저장되어있으면 더하고
}
}
}
if (sum >= 4)
{
answer++; // 4 이상 저장되었으면 정답
}
}
}
}
void rotate(int &sx, int &sy, int &cx, int &cy, int N)
{
int rx, ry;
int nsx, nsy;
for (int j = 0; j < N; j++)
{
for (int i = 0; i < N; i++)
{
temp[i][N - 1 - j] = check[j][i]; // 오른쪽으로 90도 회전한다.
if (j == cy && i == cx)
{ // 만약 현재 인덱스가 회전 중심점이라면
rx = N - 1 - j; // 변경된 회전 중심점을 각각 rx, ry에 저장
ry = i;
}
if (j == sy && i == sx)
{ // 만약 현재 인덱스가 시작점이라면
nsx = N - 1 - j; // 변경된 시작점을 저장
nsy = i; // 변경된 시작점은 다음 generation이 붙는데 사용됨
}
}
}
int dx, dy; // 이동 자리 값
dx = cx - rx;
dy = cy - ry;
nsx += dx; // 변경 시작점에 이동값을 더해서 최종 완성
nsy += dy;
//원래에 붙이기
for (int j = 0; j < N; j++)
{
for (int i = 0; i < N; i++)
{
int ny = j + dy;
int nx = i + dx;
if (0 <= nx && nx < N && 0 <= ny && ny < N)
{ // 범위를 벗어나지 않는다면
if (check[ny][nx] == 0 && temp[j][i] != 0)
{
check[ny][nx] += temp[j][i]; // 현재 좌표 계산용 check맵에 초기화
map[ny][nx] += temp[j][i]; // 결과값용 map도 초기화
}
else
{ // 범위 벗어나지 않는다면 넘어간다.
continue;
}
}
}
}
cx = nsx; // 회전 중심점을 새로운 중심점으로 초기화
cy = nsy;
}
int main()
{
int N;
scanf("%d", &N);
int x, y, d, g;
for (int i = 0; i < N; i++)
{
scanf("%d %d %d %d", &x, &y, &d, &g);
dots.push_back(make_tuple(x, y, d, g));
}
make_map(101); // 맵 만들고
calc_map(101); // 정답 계싼
printf("%d\n", answer);
//system("pause");
return 0;
}
- 어렵진 않지만 시간이 너무 오래 걸린다.