정보올림피아드 초등 - 지역예선] 2011년도 31-33번문제

 

 

 

 

 

 

 

 

 

 

 

문제풀이) main 을 분석해 본다.

int main() {   int i, j, max_height = 0;   FILE *fi = fopen("INPUT.TXT", "r");   fscanf(fi, "%d", &n);   for (i=0; i<=n+1; i++)     for (j=0; j<=n+1; j++) area[i][j] = 0; //area 변수 초기화  for (i=1; i<=n; i++)     for (j=1; j<=n; j++) {       fscanf(fi, "%d", &area[i][j]);       if (max_height < area[i][j]) max_height = area[i][j]; // area 입력 받으면서 가장 높은 지점을 max_height 에 추출하여 입력한다.    }    fclose(fi);   //area 영역을 입력 받는다.   /* 이부분에서 높이가 1 에서 max_height 까지 루프를 돌면서 잠기지 않는 영역을 찾아 내어 가장 많은 부분을 추출한다. */

따라서 (b) 에 들어갈 항목은 

 i < max_height 가 들어가면 된다.(i <= max_height 가 될 필요는 없다. i = max_heigth 인 경우 모두 잠기기 때문에 안잠기는 영역은 0 이다.)

CountArea() 함수를 분석해 본다.

int countArea( int h ) {   int i, j, cnt = 0;   for (i=0; i<=n+1; i++)   for (j=0; j<=n+1; j++) visited[i][j] = 0;  //방문영역인 visited를 초기화  for (i=1; i<=n; i++)     for (j=1; j<=n; j++)     if (area[i][j] > h && visited[i][j] == 0)  //area 의 높이가 잠기는 높이보다 높으면서 방문하지 않은 영역이면 bfs 루틴을 통해 잠기지 않는 부분을 방문한다.    {         bfs(h, i, j); //방문한 영역이 있으면 cnt 를 증가 시킨다.       cnt++;    }    return cnt; }

bfs() 함수를 분석해 본다.

 

void bfs( int h, int x, int y ) {    int qx[maxn*maxn+1], qy[maxn*maxn+1];     int front, rear, nx, ny, i;     front = rear = 0;     rear++;  qx[rear] = x; //방문하는 x 포지션을 기록 qy[rear] = y; //방문하는 y 포지션을 기록     visited[x][y] = 1;     while (front < rear) {           front++;           for (i=0; i<4; i++) {   //dx,dy 의 위치가 자신을 기준으로 위,아래,왼쪽,오른쪽 임              nx = qx[front] + dx[i];                 ny = qy[front] + dy[i];     if ((a)) {      //여기서 해당 포지션이 잠기는 높이보다 큰 경우이고 방문하지 않은 경우에만 방문위치를 설정 한다.                   rear++;          qx[rear] = nx;          qy[rear] = ny;                          visited[nx][ny] = 1;                   }             }           } }

따라서 (a) 에 들어갈 항목은

area[nx][ny] > h && visited[nx][ny] == 0 임

33번 문제를 풀기 위해서는 잠기는 위치를 1 에서 9 까지 설정 하면서

지워 보면서 문제를 풀어 본다.

높이가 7 인 경우에 6개 구역이 잠기지 않는 것을 확인 할 수 있다.