[코드트리/NOVICE MID] 체크판위에서 2 (JAVA)

🔺 문제

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

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int R, C;
    static char[][] map;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
 
        map = new char[R][C];
        for(int i = 0 ; i < R ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < C ; j++) {
                map[i][j] = st.nextToken().charAt(0);
            }
        }
 
        int cnt = 0;
        for(int i = 1 ; i < R ; i++) {
            for(int j = 1 ; j < C ; j++) {
                for(int k = i + 1 ; k < R - 1 ; k++) {    // 적어도 한 칸 이상 아래쪽 위치에 있는
                    for(int l = j + 1 ; l < C - 1 ; l++) {    // 적어도 한 칸 이상 오른쪽 위치에 
                        if(map[0][0] != map[i][j] && map[i][j] != map[k][l] && map[k][l] != map[R-1][C-1])
                            cnt++;
                    }
                }
            }
        }
 
        System.out.println(cnt);
    }
}

 

 

 

🧩  해결 아이디어

• 완전탐색

- 점프 이후 첫 번째, 두 번째로 방문하는 위치를 일일이 보며 모든 알파벳이 다른지 확인

- 시간 복잡도 : O(N^4)

1초에 대략 1억 번의 연산이 수행하다고 보고,

15^4 < 1억이므로 완전탐색으로 진행해도 괜찮다!

 

💥 유의사항

i와 j의 범위를 1이 아닌 0부터 시작하면 틀린다.

이미 (0,0)에서 출발한 상태니까 꼭 1부터 시작해야 함...!!!

 

 

 

 

---

💬 느낀 점

다음번엔 빠르게 풀쟈ㅏ....

 

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