알고리즘36 :: SWEA_추억의2048

 

꽥님의 오픈프로필

이 문제는 모든 맵의 좌표를 다 봐야 한다.

특히 자기보다 큰 수를 만났을 때는 더이상 움직이면 안된다.

0에 대해서는 예외 처리해줘야 한다. 작은 값에 대해서도 움직이지 못하게 했는데 0 을 만나면 안가서 자꾸 애먹은데서 fail이 떴다.

재귀함수를 써서 맵의 브루트포스 처리하고 범위체크와 더불어 이동간의 조건을 잘 처리해주면 쉽게 해결할 수 있다. 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
 
public class Solution {
 
    private static int tc, n;
    private static String command ="";
    private static int[][] map;
    private static int[][] visit;
     
    private static boolean  check(int x, int y) {
        if(x<0 || x>=n || y<0 || y>=n) 
            return false;
        else
            return true;
    }
    private static void DFS(int nn, int c) {
        int x = nn/n;
        int y = nn%n;
 
        if(nn<0) return ;
        int d = map[x][y]; //현재 위치의 값 
         
        if(c==2) {
            //down
            int tempx = x; //원래 위치의 인덱스 저장 
             
            x+=1;
                 
                k:while(check(x,y) && visit[x][y]==0) {
                    if(map[x][y] == d && map[x][y]!=0) { //올라 가서 현재 위치 의 값과 일치하다면
                        map[x][y] += d;
                        visit[x][y]=1;
                        map[tempx][y] = 0;
                    }else if(map[x][y]>d){ //자기값보다 크면 못올라간다. 
                        break k;
                    }else if(map[x][y]<d && map[x][y]!=0) {
                        break k;
                    }
                    else {
                        map[x][y] = d;
                        map[tempx][y]=0;
                    }
                    tempx = x; //원래 있던 좌표 
                    x+=1; //이동하는 좌표 
                }
                 
             
        }else if(c==4) {
            //left
            int tempy = y; //원래 위치의 인덱스 저장 
             
            y+=1;
                 
                k:while(check(x,y) && visit[x][y]==0) {
                    if(map[x][y] == d && map[x][y]!=0) { //올라 가서 현재 위치 의 값과 일치하다면
                        map[x][y] += d;
                        visit[x][y]=1;
                        map[x][tempy] = 0;
                    }else if(map[x][y]>d){ //자기값보다 크면 못올라간다. 
                        break k;
                    }else if(map[x][y]<d && map[x][y]!=0) {
                        break k;
                    }
                    else {
                        map[x][y] = d;
                        map[x][tempy]=0;
                    }
                    tempy = y; //원래 있던 좌표 
                    y+=1; //이동하는 좌표 
                }
        }   
        DFS(nn-1,c);
    }
     
 
    private static void DFS2(int nn, int c) {
        int x = nn/n;
        int y = nn%n;
 
        if(nn>(n-1)*n+(n-1)) return ;
        int d = map[x][y]; //현재 위치의 값 
         
        if(c==1) {
            //up
            int tempx = x; //원래 위치의 인덱스 저장 
             
            x-=1;
                 
                k:while(check(x,y) && visit[x][y]==0) {
                    if(map[x][y] == d&& map[x][y]!=0) { //올라 가서 현재 위치 의 값과 일치하다면
                        map[x][y] += d;
                        visit[x][y]=1;
                        map[tempx][y] = 0;
                    }else if(map[x][y]>d){ //자기값보다 크면 못올라간다. 
                        break k;
                    }else if(map[x][y]<d && map[x][y]!=0) {
                        break k;
                    }
                    else {
                        map[x][y] = d;
                        map[tempx][y]=0;
                    }
                    tempx = x; //원래 있던 좌표 
                    x-=1; //이동하는 좌표 
                }
                 
             
        }else if(c==3) {
            //left
            int tempy = y; //원래 위치의 인덱스 저장 
             
            y-=1;
                 
                k:while(check(x,y) && visit[x][y]==0) {
                    if(map[x][y] == d&& map[x][y]!=0) { //올라 가서 현재 위치 의 값과 일치하다면
                        map[x][y] += d;
                        visit[x][y]=1;
                        map[x][tempy] = 0;
                    }else if(map[x][y]>d){ //자기값보다 크면 못올라간다. 
                        break k;
                    }else if(map[x][y]<d && map[x][y]!=0) {
                        break k;
                    }
                    else {
                        map[x][y] = d;
                        map[x][tempy]=0;
                    }
                    tempy = y; //원래 있던 좌표 
                    y-=1; //이동하는 좌표 
                }
        }   
        DFS2(nn+1,c);
    }
    public static void main(String[] args) throws Exception{
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         
        tc = Integer.parseInt(br.readLine());
        for(int v=1; v<=tc; v++) {
        StringTokenizer st = new StringTokenizer(br.readLine());
         
        n = Integer.parseInt(st.nextToken());
        command = st.nextToken();
        map = new int[n][n];
        visit = new int[n][n]; 
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }//end of for loop
         
        int c = 0;
         
        if(command.equals("up"))
            c=1;
        else if(command.equals("down"))
            c=2;
        else if(command.equals("left"))
            c=3;
        else if(command.equals("right"))
            c=4;
         
        if(c==1 || c==3)
            DFS2(0, c);
        else
            DFS((n-1)*n+(n-1),c);
         
        System.out.println("#"+v    );
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
         
         
    }
    }
 
}