(C/C++) 백준 1074번 - Z

문제출처: https://www.acmicpc.net/problem/1074

1074번: Z

 

1. 코드

#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
 
using namespace std;
int N, r, c;
int cnt;
 
void visit(int y, int x, int n) {
    //y,x는 시작 좌표, n 한변의 길이
    //행, 열
 
    if (y == r && x == c) {
        printf("%d\n", cnt);
        return; //종료
    }
    
    //r과 c가 현재 사분면
    if (r < y + n && r >= y && c < x + n && c >= x) {
        //왼위 탐색
        visit(y, x, n / 2);
        //오위 탐색
        visit(y, x + n / 2, n / 2);
        //왼아 탐색
        visit(y + n / 2, x, n / 2);
        //오아 탐색
        visit(y + n / 2, x + n / 2, n / 2);
    }
 
    //현재 사분면에 없으면 사분면의 크기만큼 더해준다.
    else {
        cnt += n * n;
    }
}
int main() {
 
    scanf("%d %d %d", &N, &r, &c);
 
    visit(0, 0, pow(2, N));
    //한변의 길이는 2^N 
    
    return 0;
}

2. 해결과정

배열을 4등분 한후에 z모양으로 순서대로 방문해주면서 체크하면 되는 문제이다. 찾고자하는 좌표가 어느 분면에 속하는 지 알아내면 쉽게 문제를 해결할 수 있다.

찾고자 하는 좌푯값 r,c(행과 열 즉 y좌표, x좌표 순)이 현재 사분면 내에 존재하면 현재 사분면을 사등분 한 뒤에 왼위, 오위, 왼아, 오아 4개의 분면을 각각 재귀함수를 호출해주면 된다.

만약에 현재 사분면 내에 존재하지 않는 다면 해당 구역의 크기만큼 탐색한 수에 더해주면 된다.

 

3. 느낀점

최근에 푼 백준 2448번 별찍기 -11을 풀고 나서 4가지 분면으로 분할하여 좌표값을 탐색하는 문제를 풀었더니 생각보다 규칙을 찾기도 쉬웠고, 좌표값을 설정하는 것도 쉬웠다. 행과 열을 y좌표 x좌표로 설정하는 것에 살짝 고민을 하긴했는데 직접 그림을 그려서 구현하니까 금방 해결할 수 있었다.

pow를 사용했는데 비쥬얼스튜디오 상에서는 math.h를 포함하지 않아도 출력 성공을 했는데 백준에서는 계속 실패가 떠서 왜일까 고민했지만 math.h를 포함하지 않아서 컴파일오류가 떴던 걸루,,, 다른 사람들 코드를 보니 비트 연산자도 많이 사용하던데, 익숙하지 않아서,,,