이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 92 번째 글 입니다.
목차
실버1 : 구현 문제이다.
너무 짜증난다. 문제 제대로 읽어. 제발제발젭라..
- 뱀이 지나가는 경로를 잡아줄 자료구조
- map에 표시해서 갈 수 있는지 없는지 알아야 한다.
- tail의 위치를 tracking할 수 있어야 한다. -> queue
- 시간
- 현재 보고 있는 방향
- 방향에 따른 우회전 좌회전
- action을 알려줄 방향
Code
//
// main.cpp
// algorithm_prac
//
// Created by 최완식 on 2021/04/05.
//
#include <iostream>
#include <vector>
using namespace std;
int N;
int map[64][64];
vector<char> ans;
void go(int sy, int sx, int d){
int setN = map[sy][sx];
int flag = 0;
for (int i = sy; i < sy+d; i++) {
for (int j = sx; j < sx+d; j++) {
if (setN != map[i][j]) {
flag = -1;
break;
}
}
if (flag == -1) break;
}
if (flag == 0) ans.push_back(setN + '0');
else {
ans.push_back('(');
go(sy, sx, d/2);
go(sy, sx+d/2, d/2);
go(sy+d/2, sx, d/2);
go(sy+d/2, sx+d/2, d/2);
ans.push_back(')');
}
}
int main(){
cin >> N;
for (int i = 0; i < N; i++) {
char temp[64];
cin >> temp;
for (int j = 0; j < N; j++) {
map[i][j] = temp[j] - '0';
}
}
go(0, 0, N);
for (int i = 0; i < int(ans.size()); i++) {
cout << ans[i];
}
return 0;
}