격자 탐색

 

 

 

시뮬레이션 유형에서 많이 등장하는 내용이다.

 

dr = {-1, 1, 0, 0}

dc = {0, 0, -1, 1}

 

dr dc배열을 선언하고 탐색 시 사용한다. (문제에 따라 숫자를 넣는 순서는 바뀔 수 있다..)

 

 

ex.1)

 

 

 

 

배열에 그림과 같이 숫자를 넣는 경우를 생각해보자.

 

 

import java.io.*;
import java.util.*;

public class Main {

	static int[] dr = {1,0,-1,0};
	static int[] dc = {0,-1,0,1};

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		    
    int dir = 3;
    
    int[][] arr = new int[N][M];

    int r = 0;
    int c = 0;

    arr[r][c] = 1;

    int val = 1;    

    for(int i=2; i<N*M + 1; i++){
      int nr = r + dr[dir];
      int nc = c + dc[dir];

      if((nr <= -1 || nr >= N || nc <= -1 || nc >= M) || arr[nr][nc] != 0){
        dir++;
        if(dir == 4){
          dir = 0;
        }        
      }

      r = r + dr[dir];
      c = c + dc[dir];

      arr[r][c] = i;
    }


    for(int i=0; i<N; i++){
      for(int j=0; j<M; j++){
        System.out.print(arr[i][j] + " ");
      }
      System.out.println();
    }		
		
	}
}

 

 

 

dr dc배열 설정 후 dir변수를 사용해 적절히 방향을 바꿔준다.

 

 

 

이 외에도 격자에서 변하는 요소가 여러 개일 경우를 고려한다던가.. 가중치를 변경해서 적용한다던가.. 문제에 여러 가지 베리에이션이 있을 수 있는데, dr dc 테크닉을 바탕으로 문제가 요구하는 바를 잘 구현하면 된다...

 

시뮬레이션 유형은 구현과 깊게 연관되어있으니.. 변하는 요소가 여러 개일 경우는 temp_map 배열을 새로 생성해 배열을 관리한다던가, 위치를 저장하는 클래스를 하나 선언해 클래스를 통해 관리한다던가. 여러 가지 방법으로 구현할 수 있다.

 

일단은 dr dc테크닉을 숙지하고, 여러 시뮬레이션 유형 문제를 풀어서 어떤 유형의 문제가 출제되는지 손에 익히는게 중요하다.