코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
실력진단에서 백트래킹 파트에서의 부족한 점을 알게 되었으나 그 전 미리 진행해놓은 부분이 있기에 그 파트 먼저 작성하도록 하였습니다.
#include <bits/stdc++.h>
using namespace std;
int n, m, t;
int arr[25][25];
int cnt[25][25];
int nxtCnt[25][25];
// 상하좌우 순으로 탐색용
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
bool InRange(int nx, int ny) {
// 범위에서 벗어날 경우 false 리턴
return (0 <= nx && nx < n && 0 <= ny && ny < n);
}
void Move(int i, int j) {
int nxt_i = i;
int nxt_j = j;
int maxVal = 0;
// 상하좌우 중 가장 큰 값이 있는 위치를
// nxt_i , nxt_j에 저장
for (int dirNum = 0; dirNum < 4; dirNum++) {
int nx = i + dx[dirNum];
int ny = j + dy[dirNum];
if (InRange(nx, ny) && arr[nx][ny] > maxVal) {
nxt_i = nx;
nxt_j = ny;
maxVal = arr[nx][ny];
}
}
// nxt_i, nxt_j 위치 값 증가 즉, 구슬 이동
nxtCnt[nxt_i][nxt_j]++;
return;
}
void RemoveDup() {
// nxtCnt의 값이 2 이상인 부분은 구슬이 2개이상 있는 위치임
// 그 부분을 없애도록 함
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (nxtCnt[i][j] >= 2) nxtCnt[i][j] = 0;
}
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> t;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
}
}
// 구슬의 위치 입력받아 cnt배열 값 증가
int r = 0;
int c = 0;
for (int i = 0; i < m; i++) {
cin >> r >> c;
cnt[r - 1][c - 1]++;
}
// t초간 진행
while (t--) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
nxtCnt[i][j] = 0;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 모든 구슬을 움직임
if (cnt[i][j] == 1) Move(i, j);
}
}
/*
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << nxtCnt[i][j] << " ";
}
cout << "\n";
}
*/
// 구슬이 움직인 이후 겹치는 부분 삭제
RemoveDup();
// 구슬 움직인 이후 위치를 cnt에 저장
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cnt[i][j] = nxtCnt[i][j];
}
}
}
// 구슬 개수 ans에 더함
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
ans += cnt[i][j];
}
}
cout << ans;
}
n,m,t를 각각 입력받고 2중 for문을 통해 2차원 배열 arr의 값을 채웁니다.
m번 만큼 r,c 값을 입력받아 cnt 배열(구슬 위치 저장용) 의 값을 증가시킵니다.
while문을 통해 t초간 움직임을 반복할 수 있도록 합니다.
이중 for문을 통해 nxtCnt(다음 구슬 위치 저장용)을 일단 초기화 시키고(for문 진행시 구슬 위치 남아
있는 것 방지용) cnt에서 구슬이 위치한 부분의 좌표로 Move() 함수를 호출시킵니다.
Move() 함수는 구슬 위치 기준 상하좌우 4방향을 탐색하여 그 중 가장 큰 수의 좌표를 찾아 nxtCnt 배열에서
그 좌표 부분의 값을 1 증가시킵니다.(구슬 이동)
이후 RemoveDup() 함수를 통해 모든 구슬을 이동시킨 후 위치를 알려주는 nxtCnt 배열에서
값이 2 이상인 부분 즉, 구슬이 같은 위치에 존재하는 경우를 찾아 이를 없앱니다.
이후 nxtCnt 배열을 cnt 배열에 복사해 이동 후 구슬 위치를 저장합니다.
마지막으로 cnt배열에서 구슬이 남아있는 부분의 수를 세어 ans에 저장합니다.
----- 진행 중 문제
위 문제를 진행할 때 가장 많이 오류를 만났던 부분은 Move()함수 부분이였습니다.
-------------------수정 전 Move----------------------------
void Move(int i, int j) {
int nxt_i = i;
int nxt_j = j;
int maxVal = arr[i][j];
// 상하좌우 중 가장 큰 값이 있는 위치를
// nxt_i , nxt_j에 저장
for (int dirNum = 0; dirNum < 4; dirNum++) {
int nx = i + dx[dirNum];
int ny = j + dy[dirNum];
if (InRange(nx, ny) && arr[nx][ny] > maxVal) {
nxt_i = nx;
nxt_j = ny;
maxVal = arr[nx][ny];
}
}
// nxt_i, nxt_j 위치 값 증가 즉, 구슬 이동
nxtCnt[nxt_i][nxt_j]++;
return;
}
------------------------수정 후 Move()----------------------------
void Move(int i, int j) {
int nxt_i = i;
int nxt_j = j;
int maxVal = 0;
// 상하좌우 중 가장 큰 값이 있는 위치를
// nxt_i , nxt_j에 저장
for (int dirNum = 0; dirNum < 4; dirNum++) {
int nx = i + dx[dirNum];
int ny = j + dy[dirNum];
if (InRange(nx, ny) && arr[nx][ny] > maxVal) {
nxt_i = nx;
nxt_j = ny;
maxVal = arr[nx][ny];
}
}
// nxt_i, nxt_j 위치 값 증가 즉, 구슬 이동
nxtCnt[nxt_i][nxt_j]++;
return;
}수정 전과 수정 후 딱 하나의 차이가 존재하는 데 바로 maxVal의 초기화 값 부분입니다.
위 문제는 구슬 주위 4방향에서 가장 큰 값으로 이동하는 문제인데 문제를 제대로 읽지 않아
4방향 중 "구슬 위치 값보다 큰 값 중 가장 큰 값"으로 이동하는 것으로 착각하여 많이 틀렸던 문제 같습니다.
항상 귀찮다고 문제를 대충 읽고 넘어가는 경향이 있는데 이 습관을 좀 바로 잡아야할 것 같습니다.
