BOJ - 뱀(3190)

실버1 : 구현 문제이다.

너무 짜증난다. 문제 제대로 읽어. 제발제발젭라..

1. 뱀이 지나가는 경로를 잡아줄 자료구조
   1. map에 표시해서 갈 수 있는지 없는지 알아야 한다.
   2. tail의 위치를 tracking할 수 있어야 한다. → queue
2. 시간
3. 현재 보고 있는 방향
4. 방향에 따른 우회전 좌회전
5. 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;
}
 
 

Reference

• 백준(3190번) - 뱀