The Grid Search

문제: The Grid Search

난이도: Medium

 

문제 설명

 그리드와 패턴이 주어졌을 때, 주어진 패턴이 그리드 안에 존재하는지를 확인하여 존재하면 “YES”를, 아니면 “NO”를 출력하라.

 예를 들어, 그리드와 패턴이 다음과 같이 주어졌다고 가정하자.

 

그리드(10행10열)

7283455864

6731158619

8988242643

3830589324

2229505813

5633845374

6473530293

7053106601

0834282956

4607924137

패턴(3행 4열)

9505

3845

3530

 

  그리드 안에 패턴이 있으므로 YES이다.

문제 해결

소스 코드

    static String gridSearch(String[] G, String[] P) {
        int gWidth = G[0].length();
        int gHeight = G.length;
        int pWidth = P[0].length();
        int pHeight = P.length;

        boolean scanFlag = false;
        int scanI = 0;
        int scanJ = 0;
        String result = "NO";

        loop:
        for(int i = 0; i < gHeight - pHeight + 1; i++) {
            for(int j = 0; j < gWidth - pWidth + 1; j++) {
                if(G[i].substring(j, j+pWidth).equals(P[0])) {
                    scanFlag = true;
                    scanI = i;
                    scanJ = j;
                }
                if(scanFlag) {
                    for(int k = 0; k < pHeight; k++) {
                        if(!G[scanI + k].substring(scanJ, scanJ+pWidth).equals(P[k])) {
                            scanFlag = false;
                            break;
                        }
                        if(k == pHeight-1) {
                            result = "YES";
                            break loop;
                        }
                    }
                }
            }
        }

        return result;
    }

 

해설

 가장 먼저 그리드 안에 패턴의 1행(P[0])이 존재하는지를 확인한다. 만약 존재한다면, 그 부분의 아래 방향으로 부분적으로 탐색하여 패턴의 다른 행 과도 일치하는지를 확인한다. 한 행이라도 맞지 않다면 부분적인 탐색을 끝내고, 그리드 내에 패턴의 1행과 맞는 다른 부분이 있는가를 다시 확인한다. 패턴이 그리드 내에 있는게 확실하다면 맨 처음에 “NO”로 초기화된 결과 값을 “YES”로 바꾸고 반복문 전체를 빠져나간다.