1861. 정사각형 방(D4) 본문
사실 이 문제는 Testcase가 약해서 사용한 방법대로 시작점을 정하지 않고
맵의 모든 점을 시작점으로 해도 시간 내에 정상적으로 동작하지만
1 |
2 |
3 |
4 |
5 |
6 |
12 |
11 |
10 |
9 |
8 |
7 |
13 |
14 |
15 |
16 |
17 |
18 |
24 |
23 |
22 |
21 |
20 |
19 |
25 |
26 |
27 |
28 |
29 |
30 |
36 |
35 |
34 |
33 |
32 |
31 |
만약 맵이 위와 같은 모양이라면 최대 200 * 200 사이즈에서 시간초과가 나게 된다.
1에서 dfs를 통해 36까지 확인하게 되고 2에서도 마찬가지, 3에서도, 4에서도 .... 의 과정을 거치게 되기 때문이다.
따라서 시작점을 정해주게 되면 주석으로 추가해놓은 내용처럼 시작점의 개수를 줄일 수 있고 그만큼
함수 호출 횟수를 줄일 수 있다.
- 소스 코드 -
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | import java.util.Scanner; public class Solution1861 { static int dx[]= {0,0,1,-1}; static int dy[]= {1,-1,0,0}; static int map[][]; static int count; static int dfs(int x,int y,int tempCount) { // 좌표를 받고 주변 4칸을 확인해서 다음으로 갈 칸이 있다면 // 해당 칸으로 함수를 실행합니다. boolean flag=false; for(int i=0;i<4;i++) { // 주변 4칸을 확인해서 if(map[x+dx[i]][y+dy[i]]==map[x][y]+1) { // 갈 수 있는 곳이 있다면 flag=true; tempCount=dfs(x+dx[i],y+dy[i],tempCount)+1; // 해당 칸의 dfs 실행 } } if(!flag) return 1; // 더이상 이동할 칸이 없으므로 1 반환 else return tempCount; } public static void main(String[] args) { Scanner scan=new Scanner(System.in); int T=scan.nextInt(); for(int test_case=1;test_case<=T;test_case++) { int n=scan.nextInt(); map=new int[n+2][n+2]; count=1; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { map[i][j]=scan.nextInt(); } } int resultX=0; int resultY=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { boolean plusCheck=false; boolean minusCheck=true; for(int k=0;k<4;k++) { // 주변 4칸을 확인해서 /////////// (1) 자신보다 1 큰 칸이 있고 /////////// if(map[i+dx[k]][j+dy[k]]==map[i][j]+1) plusCheck=true; /////////// (2) 자신보다 1 작은 칸이 없다면 시작점으로 한다. /////////// if(map[i+dx[k]][j+dy[k]]!=0&& // 0인경우는 벽이므로 제외 map[i+dx[k]][j+dy[k]]==map[i][j]-1) minusCheck=false; } //////////// 시작점 개수 변화 /////////// // size 200짜리 테스트케이스 (전체 시작점으로 할 시 40000개) // (1) 조건 거칠 경우 : 40000 -> 39852 // (2) 조건 거칠 경우 : 39852 -> 148 if(plusCheck && minusCheck) { int temp=dfs(i,j,0); if(temp>count) { // 만약 새로운 시작점에 대해 dfs값이 더 크다면 갱신 resultX=i; resultY=j; count=temp; }else if(temp==count) { // dfs값이 같다면 해당 칸의 값을 비교하여 더 작은 값으로 갱신 if(map[resultX][resultY]>map[i][j]) { resultX=i; resultY=j; } } } } } System.out.printf("#%d %d %d\n",test_case,map[resultX][resultY],count); } scan.close(); } } | cs |
'알고리즘 문제풀기 > SW Expert Academy' 카테고리의 다른 글
7193. 승현이의 수학공부(D3) (0) | 2019.03.06 |
---|---|
1868. 파핑파핑 지뢰찾기(D4) (0) | 2019.03.06 |
6960. 자영이의 퍼스트 솔브(D6) (0) | 2019.02.26 |
1907. 모래성 쌓기 (D5) (0) | 2019.01.25 |
5521. 상원이의 생일파티 (D5) (0) | 2019.01.17 |
Comments