[코드트리/NOVICE MID] 숨은 단어 찾기 2 (JAVA)

🔺 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {1, 0, -1, -1, -1, 0, 1, 1};    // 8방향
    static int[] dy = {-1, -1, -1, 0, 1, 1, 1, 0};
 
    static int N, M, cnt;
    static char[][] words;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        // 입력받기
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        words = new char[N][M];
 
        for(int i = 0 ; i < N ; i++) {
            char[] ch = br.readLine().toCharArray();
            for(int j = 0 ; j < M ; j++) {
                words[i][j] = ch[j];
            }
        }
 
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                if(words[i][j] != 'L')  continue;
 
                for(int d = 0 ; d < 8 ; d++) {    // 8방향 탐색
                    int x = i;
                    int y = j;
                    int tmpCnt = 1;
 
                    while(true) {
                        int nx = x + dx[d];
                        int ny = y + dy[d];
 
                        if(inRange(nx, ny) && words[nx][ny] == 'E') { // 조건을 만족하는 경우에만 'LEE' 만들 수 있음
                            tmpCnt++;
                            
                            if(tmpCnt == 3) {
                                cnt++;
                                break;
                            }
                        }
                        else
                            break; 
 
                        // 현재 위치 갱신
                        x = nx;
                        y = ny;                          
                    }
                }                
            }
        }
 
        System.out.println(cnt);
    }
 
    // 범위 확인용 메소드
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < N && 0 <= y && y < M);
    }
}

 

 

 

🧩  해결 아이디어

• 완전탐색 (자리 수 단위 완전탐색) + dx dy technique

- 각 칸의 값이 'L'이라면 주변 8방향 탐색을 수행한다.

- 다음 값이 'E'라면 해당 방향으로 계속 탐색하다가 격자 크기를 벗어나거나 'E'가 아닌 다른 값이 나오면 탐색을 멈춘다.

 

 

💥 유의사항

- 8방향 완전탐색 (가로, 세로, 대각선)

 

 

 

---

🔺 다른 풀이들

- 굳이 2차원 배열을 만들지 않아도 된다. 1차원 배열에서 해도 됨!

순서가 조금 다르긴 한데 전체적 맥락은 비슷함!

import java.util.Scanner;
 
public class Main {
    public static final int DIR_NUM = 8;
    public static final int MAX_N = 100;
    
    public static int n, m;
    public static String[] arr = new String[MAX_N];
    
    public static int[] dx = new int[]{1, 1, 1, -1, -1, -1, 0, 0};
    public static int[] dy = new int[]{-1, 0, 1, -1, 0, 1, -1, 1};
    
    public static boolean inRange(int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < m;
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i = 0; i < n; i++)
            arr[i] = sc.next();
        
        int cnt = 0;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++) {
                if(arr[i].charAt(j) != 'L') continue;
                
                for(int k = 0; k < DIR_NUM; k++) {
                    int tmpCnt = 1;
                    int curx = i;
                    int cury = j;
 
                    while(true) {
                        int nx = curx + dx[k];
                        int ny = cury + dy[k];
 
                        if(!inRange(nx, ny))    break;
                        if(arr[nx].charAt(ny) != 'E')    break;
 
                        // 격자 범위 안에 있고, 다음 단어가 'E'인 경우, 갯수와 현재 위치 갱신
                       tmpCnt++;
                        curx = nx;
                        cury = ny;
                    }
 
                    // LEE를 만들었다면, 정답 + 1
                    if(tmpCnt >= 3) {
                        cnt++;
                    }
                }
            }
        
        System.out.print(cnt);
    }
}

 

---

💬 느낀 점

8방향...

dx dy 배열 값 순서를 다르게 작성했더니 자꾸 1씩 답이 틀리게 나오는거다...

그래서 환장하는 줄 알았다...ㅠ

 

복습을 철저히 하는 것으로....

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[코드트리 챌린지] 자리 수 단위로 완전탐색_연습문제 & 테스트