[Algorithm/Java] 백준 17500 국경

https://www.acmicpc.net/problem/17500

17500번: 국경

 

보통 배열은 칸으로 움직이는데 이 문제는 꼭지점,선분을 이어서 움직여야해서 처음에 어떻게해야할지 고민이었다.

일단 N이 최대가 4여서 모든 경우를 다 해보면 될 것 같았다.

N*N 배열을 (2*N+1)*(2*N+1)로 늘려서 나라가 되는 부분과 국경과 될수 있는 부분을 모두 배열로 치고 나라 부분을 경계로 두고 목적지 까지 갈 수 있는 모든 경로를 백트래킹으로 탐색했다.

나라부분이 벽인(visit[i][j]=1) 도로 dfs 문제 이런느낌으로 생각했다. 

 

국경을 visit[i][j]=1, 나라부분을 visit[i][j]=2로 두고 

백트래킹으로 끝지점에 도착했을 때의 상태에서 visit[i][j]=2인데 '.'이 아닌 곳에서 checkdfs를 다시 돌려줬다.

국경내부에 있는 갈 수 있는 모든곳을 탐색해서 나라부분이 '.'이 아닌 다른 알파벳이면 false ..

checkdfs부분에서 새로운 visit배열을 써야해서 tmp에 담아줬다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Border{
    static int N;
    static int M;
    static char[][] map;
    static char[][] newMap;
    static int[][] visit;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    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 = 2*N+1;
        map = new char[N][N];
        newMap = new char[2*N+1][2*N+1];
        visit = new int[2*N+1][2*N+1];
        for(int i=0; i<N; i++){
            String str = br.readLine();
            for(int j=0; j<N; j++){
                map[i][j] = str.charAt(j);
            }
        }
        // 입력받은 값으로 newMap, visit을 생성해줌 
        for(int i=0; i<M; i++) {
            for(int j=0; j<M; j++){
                if((i%2==0) && j%2==0) newMap[i][j]='+';
            }
        }
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                newMap[2*i+1][2*j+1] = map[i][j];
                visit[2*i+1][2*j+1]=2;
            }
        }


        //모든 경우를 탐색해서 [2n][2N]에 도착할때 확인
        visit[0][0]=1;
        boolean result = dfs(0,0);
        
        // 결과출력 
        if(result) {
            System.out.println("yes");
            for(int i=0; i<4*N+3; i++) System.out.print("#");
            System.out.println("");
            for(int i=0; i<M; i++){
                System.out.print("#");
                if(i%2==0) {
                    for(int j=0; j<M; j++){
                        if(newMap[i][j]=='+') System.out.print('+');
                        else if(visit[i][j]==1) {
                            System.out.print("---");
                        }
                        else System.out.print("   ");
                    }
                }
                else {
                    for (int j = 0; j <M; j++) {
                        if (visit[i][j] == 2) System.out.print(" "+newMap[i][j]+" ");
                        else if (visit[i][j] == 1) {
                            System.out.print("|");
                        }
                        else System.out.print(" ");
                    }
                }
                System.out.println("#");
            }
            for(int i=0; i<4*N+3; i++) System.out.print("#");
        }
        else {
            System.out.println("no");
        }
    }
    
    
    
    public static boolean dfs(int x, int y) {
        if( x==2*N && y==2*N) {
          // 끝점에 도착하면 check
            return check();
        }
      // 끝점이 아니라면 갈 수 있는 경로 탐색
        for(int i=0 ;i<4; i++){
            int A = x+dx[i];
            int B = y+dy[i];
            if(A>=0 &&B>=0 && A<=2*N && B<=2*N && visit[A][B]==0) {
              //백트래킹으로 모든 경로 확인 
                visit[A][B]=1;
              // 탐색으로 하나라도 true를 찾았다면 리턴
                if(dfs(A,B)) return true;
                visit[A][B]=0;
            }
        }
        return false;
    }
    public static boolean check(){
      // 만들어낸 국경이 조건에 부합하는지 확인 
        int [][] tmp = new int[M][M];
        for(int i=0; i<M; i++){
            for(int j=0; j<M; j++){
                tmp[i][j] = visit[i][j];
            }
        }
        for(int i=0; i<M; i++){
            for(int j=0; j<M; j++){
                if(tmp[i][j]==2 && newMap[i][j]!='.') {
                  // 나라를 발견하면 국경에 쌓여있는 부분에 해당 나라와 같은것만 있는지 확인. 다른게 있으면 바로 false 리턴 
                    if(checkdfs(i, j, tmp, newMap[i][j])==false)
                        return false;
                }
            }
        }
        return true;
    }
    public static boolean checkdfs(int x, int y, int[][] tmp, char c){
        tmp[x][y]=1;
        for(int i=0; i<4; i++){
            int A= x+dx[i];
            int B=y+dy[i];
            if(A>=0 &&B>=0 && A<=2*N && B<=2*N && tmp[A][B]!=1 ) {
              // .이 아닌 나라가 c와 다르면 false
              if(A%2==1 && B%2==1 && newMap[A][B]!='.' && newMap[A][B]!=c)
                    return false;
                else if(checkdfs(A,B,tmp,c)==false)
                    return false;
            }
        }
        return true;
    }
}

 

틀렸던부분

- 나라가 될 수 있는 부분을 visit[i][j]=2로 지정해놨었는데 '.'인경우에는 조건문으로 확인하지않고 어떤 알파벳값일경우에만 dfs탐색하거나 조건문 확인했어야했다.