[PCCP] 시뮬레이션 (Simulation) [0]

▼ Why ?

알고리즘은 문제가 제시한 상황에 맞게 나의 생각을 소스코드로 구현(Implementation)하는 능력을 먼저 키워야 한다고 한다. 구현해내는 문제의 대표적인 유형들 중 하나가 시뮬레이션(Simulation) 문제이다. 그렇기에 시뮬레이션 관련 문제들을 먼저 차례차례 풀어나가보려고 한다.

• 시뮬레이션은 문제가 제시한 규칙에 따라 개체를 이동시키는 알고리즘이라고 할 수 있기 때문에,
  방향배열(dx, dy)을 만들어 네 방향을 탐색하는 방법을 기억해두자 !

char[] dir = {'N', 'E', 'S', 'W'};
int[] dx = {-1, 0, 1, -1};
int[] dy = {0, 1, 0, -1};

➜ 수학에서의 좌표평면과 다르게 dx는 행을, dy는 열을 의미한다 !

➜ 주변을 체크해야 하는 문제라면, 방향을 북쪽(N)부터 시계방향으로 체크하자

---

▼ 웅덩이

 

문제 정보

• 매개변수 nums에 n행 n열의 이차원 배열에 격자판 정보가 주어집니다.
  각 격자에는 그 지역의 높이가 쓰여있습니다.
  각 지역은 상하좌우 인접한 지역의 숫자가 모두 자신보다 클 경우 이 지역을 웅덩이 지역이라고 합니다.
  격자의 가장자리는 1000으로 초기화 되었다고 가정한다.
  만약 5*5 이차원 배열의 격자판 정보다 아래와 같다면 총 웅덩이의 수는 5개입니다.

• 주어진 격자에 웅덩이가 몇 개 있는지 찾아 그 개수를 반환하는 프로그램을 작성하세요.
  
  

입출력 예

 

제한사항

• 3 <= n <= 10
• 배열 nums의 원소는 자연수입니다. 1 <=  nums[i][j] <= 100

 

어떻게 해결해야 할까?

1. 구현 문제 !
2. 방향배열을 생성하고 이를 이용하여 현재 좌표를 중심으로 네 방향을 체크
3. 다음 좌표로 이동하기 전에 현재 좌표가 웅덩이인지 유효성을 검사하는 변수 ' flag ' 생성
4. 이동할 때 격자판 밖으로 벗어날 수 없는 제약이 있기 때문에, ' IndexOutOfBounds Error ' 를 방지하기 위해서 임시좌표값을 넣을 변수 ' nx ',  ' ny ' 를 생성하여 다음 좌표로 이동하기 전에 해당 좌표로 이동해도 안전한지 미리 체크하자

 

해결 코드

import java.util.*;

public static int solution(int[][] nums) {
        int n = nums.length;
        int[] dx = {-1, 0, 1, 1};
        int[] dy = {0, 1, 0, -1};
        boolean flag;
        int poolCount = 0;
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                flag = true;
                
                for(int k = 0; k < 4; k++) {
                    int nx = i + dx[j]; int ny = i + dy[j];
                    
                    if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                    
                    if(num[nx][ny] <= num[i][j]) { // 같은 경우도 고려
                        flag = false;
                        break;
                    }
                }
                
                if(flag) poolCount++;
            }
        }
        
        return poolCount;
    }

 

---

▼ 정리

• 이번 문제는 제시한 내용이 간단하고 구현하기 어렵지 않은 문제였지만, 요구사항이 많아질수록 구현 나이도가 올라갈 것이기 때문에 지속적인 반복을 통해서 생각한 것을 구현하는 과정에 빠르게 익숙해질 필요가 있을 것 같다