Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 30 | 31 |
Tags
- 삼성SW 역량 테스트 기출문제
- Programmers
- 용어 정리
- 브루트포스
- 15651c++
- backtracking
- 백준 알고리즘
- MySQL
- BFS
- 삼성 SW역량 테스트
- DFS
- 프로그래머스
- 백트레킹
- C++
- 15651
- fill함수
- 백준 15651
- 주식 용어
- 백준
- 에라토스테네스의 체
- 백준 2370
- 위상정렬
- 주린이
- 백준알고리즘
- 백준 1697
- 삼성 SW 역량 테스트 기출 문제
- 주식 용어 정리
- DP
- 2370 c++
- 시장 선거 포스터 c++
Archives
- Today
- Total
빠켱이
백준 12100번 2048(Easy)[C++] - 삼성SW 역량 테스트 기출문제 본문
12100번은 브루트 포스 알고리즘 문제입니다.
위아래 왼쪽 오른쪽의 방향을 모두 탐색해서 결과를 도출하는 문제입니다.
코드를 구현하다 보니 재귀 함수와 방향을 이동하는 함수를 하나로 짜버렸는데,
재귀 함수와 이동 함수를 나누어 짜면 가독성에 좋을 것 같습니다.
숫자를 한 방향으로 이동했을 때 두 개의 숫자를 합치는 것과 공백을 고려하는 것은 queue를 사용하여 해결하였습니다.
고려사항 1. 두 개의 숫자만을 합쳐주는 것
해당 방향의 숫자들을 적절한 순서로 queue에 넣습니다.
(ex. 위로 이동하는 방향이면 위에서부터 아래로 queue에 대입)
queue를 앞에서 부터 탐색하며 조건에 맞게 위부터 채워나감니다.
고려사항 2. 공백 처리
queue를 사용하지 않으면 공백의 여부를 따로 처리해줘야 하지만
해당 코드에서는 빈 공간의 값이 0이므로 0이면 queue에 들어가지 않습니다.
따라서 queue를 사용하면 공백을 신경 쓰지 않고 짤 수 있기 때문에 좀 더 편리한 것 같습니다.
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int n, result = 0;
int sudoku[21][21] = {0};
int d[4] = {0,1,2,3}; //0:상, 1:하, 2:좌, 3:우
void move(int dir, int count){
if(count == 5){ //5번 움직임
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
result = max(result, sudoku[i][j]);
return;
}
int copy_sudoku[21][21] = {0};
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
copy_sudoku[i][j] = sudoku[i][j]; //현재 배열 복사
if(dir == 0){ //상
for(int i = 0; i < n; i++){
queue<int> q;
for(int j = 0; j < n; j++){
if(copy_sudoku[j][i])
q.push(copy_sudoku[j][i]); //공백 제외한 숫자 q에 넣음
sudoku[j][i] = 0; //스도쿠판 초기화
}
int j = 0;
while(!q.empty()){
if(q.size() >= 2){ //queue에 2개 이상일 때
int tmp = q.front();
q.pop();
if(tmp == q.front()){ //두개의 값이 같을 때
sudoku[j++][i] = q.front() * 2; //첫번째 값 * 2 대입
q.pop();
}
else //두개의 값이 다를 때
sudoku[j++][i] = tmp;
}
else{ //queue에 1개일 때
sudoku[j++][i] = q.front(); //첫번째 값 대입
q.pop();
}
}
}
}
else if(dir == 1){ //하
for(int i = 0; i < n; i++){
queue<int> q;
for(int j = n-1; j >= 0; j--){
if(copy_sudoku[j][i])
q.push(copy_sudoku[j][i]);
sudoku[j][i] = 0;
}
int j = n-1;
while(!q.empty()){
if(q.size() >= 2){
int tmp = q.front();
q.pop();
if(tmp == q.front()){
sudoku[j--][i] = q.front() * 2;
q.pop();
}
else
sudoku[j--][i] = tmp;
}
else{
sudoku[j--][i] = q.front();
q.pop();
}
}
}
}
else if(dir == 2){ //좌
for(int i = 0; i < n; i++){
queue<int> q;
for(int j = 0; j < n; j++){
if(copy_sudoku[i][j])
q.push(copy_sudoku[i][j]);
sudoku[i][j] = 0;
}
int j = 0;
while(!q.empty()){
if(q.size() >= 2){
int tmp = q.front();
q.pop();
if(tmp == q.front()){
sudoku[i][j++] = q.front() * 2;
q.pop();
}
else
sudoku[i][j++] = tmp;
}
else{
sudoku[i][j++] = q.front();
q.pop();
}
}
}
}
else if(dir == 3){ //우
for(int i = 0; i < n; i++){
queue<int> q;
for(int j = n-1; j >= 0; j--){
if(copy_sudoku[i][j])
q.push(copy_sudoku[i][j]);
sudoku[i][j] = 0;
}
int j = n-1;
while(!q.empty()){
if(q.size() >= 2){
int tmp = q.front();
q.pop();
if(tmp == q.front()){
sudoku[i][j--] = q.front() * 2;
q.pop();
}
else
sudoku[i][j--] = tmp;
}
else{
sudoku[i][j--] = q.front();
q.pop();
}
}
}
}
for(int i = 0; i < 4; i++)
move(i, count+1);
for(int k = 0; k < n; k++)
for(int j = 0; j < n; j++)
sudoku[k][j] = copy_sudoku[k][j]; //변경 전으로 배열 복귀
}
int main(){
scanf("%d", &n);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
scanf("%d", &sudoku[i][j]);
for(int i = 0; i < 4; i++)
move(i, 0);
printf("%d", result);
}
'알고리즘 > 백준 알고리즘' 카테고리의 다른 글
백준 13460번 구슬 탈출 2[C++] - 삼성SW 역량 테스트 기출문제 (0) | 2021.02.08 |
---|---|
백준 3190번 뱀[C++] - 삼성SW 역량 테스트 기출문제 (0) | 2021.02.05 |
백준 20055번 컨베이어 벨트 위의 로봇[C++] - 삼성SW 역량 테스트 기출문제 (0) | 2021.02.04 |
백준 14891번 톱니바퀴[C++] - 삼성SW 역량 테스트 기출문제 (0) | 2021.02.03 |
백준 13458번 시험감독[C++] - 삼성SW 역량 테스트 기출문제 (0) | 2021.02.02 |
Comments