Baekjoon[17472] - 다리 만들기 2

링크

17472번: 다리 만들기 2

 

문제설명

• 다리를 만들고 섬이 연결되어있는지 확인

문제풀이

• 다리만들기(완전탐색) + 연결성 확인(DFS) + 수직다리 수평다리 따로따로 구분해서 생각해줘야함

문제코드

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


public class Main17472 {

    public static int[][] dir = {
            {-1,0},
            {1,0},
            {0,-1},
            {0,1}
    };

    public static int Ans=Integer.MAX_VALUE;
    public static int Temp;
    public static int N;
    public static int M;
    public static int[][] map;
    public static int[][] v_map;
    public static int[][] h_map;
    public static boolean[][] visit;
    public static int isize;
    public static int temp_isize;

    public static void DFS(int[] rc,int now_dir) {

        visit[rc[0]][rc[1]] = true;
        if(map[rc[0]][rc[1]]==1)temp_isize++;

        int nr;
        int nc;

        for (int d = 0; d < 4; d++) {

            nr = rc[0]+dir[d][0];
            nc = rc[1]+dir[d][1];
//            경계 안에서
            if (nr>=0 && nr<N && nc>=0 && nc<M) {
//                from 섬
                if(map[rc[0]][rc[1]]==1) {
//                    to 섬
                    if(map[nr][nc]==1 && !visit[nr][nc]) {
                        DFS(new int[] {nr,nc},d);
                    }
//                    to 수직다리
                    if(v_map[nr][nc]==1) {
                        DFS(new int[] {nr,nc},d);
                    }
//                    to 수평다리
                    if(h_map[nr][nc]==1) {
                        DFS(new int[] {nr,nc},d);
                    }
                }
//                from 수직 다리
                if((now_dir==0 || now_dir==1) && v_map[rc[0]][rc[1]]==1) {
//                    to 섬 + 수직방향으로만 가야함
                    if(now_dir == d && map[nr][nc]==1 && !visit[nr][nc]) {
                        DFS(new int[] {nr,nc},d);
                    }
//                    to 수직다리
                    if(now_dir == d && v_map[nr][nc]==1) {
                        DFS(new int[] {nr,nc},d);
                    }
                }
//                from 수평 다리
                if((now_dir==2 || now_dir==3) && h_map[rc[0]][rc[1]]==1) {
//                    to 섬 + 수평방향으로만 가야함
                    if(now_dir == d && map[nr][nc]==1 && !visit[nr][nc]) {
                        DFS(new int[] {nr,nc},d);
                    }
//                    to 수평다리
                    if(now_dir == d && h_map[nr][nc]==1) {
                        DFS(new int[] {nr,nc},d);
                    }
                }
            }
        }
    }

    public static boolean is_connected() {
        int r=0;
        int c=0;

        top:
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(map[i][j]==1) {
                    r=i;
                    c=j;
                    break top;
                }
            }
        }

//        탐색하면서 1인 칸 세아리고, 1인칸 갯수가 전체 1의 갯수와 같다면
        temp_isize=0;
        visit = new boolean[N][M];
        DFS(new int[] {r,c},0);

        if(isize==temp_isize) {
            return true;
        }
        else{
            return false;
        }
    }

    public static int is_settable(int[] rc, int now_dir) {
//        -1: 불가능 , 0~1: 다리설치못하는 길이, 2:다리 설치가능
        int sr = rc[0];
        int sc = rc[1];
        int nr;
        int nc;
        int length=0;

        while(true) {
            nr = sr+dir[now_dir][0];
            nc = sc+dir[now_dir][1];


            if(nr>=0 && nr<N && nc>=0 && nc<M) {
//                이미 설치된 경우
                if(((now_dir==0 || now_dir ==1) && v_map[nr][nc]==1) || ((now_dir==2 || now_dir ==3) && h_map[nr][nc]==1)) {
                    return -1;
                }
                if(map[nr][nc]==1) {
                    return length;
                }
                length++;
                sr = nr;
                sc = nc;
            }
            else {
                return -1;
            }
        }
    }

    public static void setBridge(int[] rc, int now_dir, int blen) {
        int sr = rc[0];
        int sc = rc[1];
        int nr;
        int nc;

//        수직
        if(now_dir==0 || now_dir==1) {
            for (int i = 0; i < blen; i++) {
                nr = sr+dir[now_dir][0];
                nc = sc+dir[now_dir][1];
                v_map[nr][nc]=1;
                sr = nr;
                sc = nc;
            }
        } 
//        수평
        else if(now_dir==2 || now_dir==3) {
            for (int i = 0; i < blen; i++) {
                nr = sr+dir[now_dir][0];
                nc = sc+dir[now_dir][1];
                h_map[nr][nc]=1;
                sr = nr;
                sc = nc;
            }
        }
    }

    public static void resetBridge(int[] rc, int now_dir, int blen) {
        int sr = rc[0];
        int sc = rc[1];
        int nr;
        int nc;

//        수직
        if(now_dir==0 || now_dir==1) {
            for (int i = 0; i < blen; i++) {
                nr = sr+dir[now_dir][0];
                nc = sc+dir[now_dir][1];
                v_map[nr][nc]=0;
                sr = nr;
                sc = nc;
            }
        }
        else if(now_dir==2 || now_dir==3) {
            for (int i = 0; i < blen; i++) {
                nr = sr+dir[now_dir][0];
                nc = sc+dir[now_dir][1];
                h_map[nr][nc]=0;
                sr = nr;
                sc = nc;
            }
        }
    }

    public static void Search(int[] rc, int now_dir) {
//        끝까지 전부 탐색
        if(rc[0]==N-1 && rc[1]==M) {
//            모든 섬 다 연결되었으면
            if(is_connected()) {
                Ans = Math.min(Ans, Temp);
            }
            return;
        }

//        좌표이동
        if(rc[1]==M) {
            rc[0]++;
            rc[1]=0;
        }

        int blen=0;
//        섬 구역이면
        if(map[rc[0]][rc[1]]==1) {
//            4방으로 설치가능여부 판단
            if(Ans<=Temp)return;
            if(now_dir<4) {
                blen = is_settable(new int[] {rc[0],rc[1]},now_dir);
//                설치 가능한 경우
                if(blen>=2) {
//                    다리 설치했을 때
                    setBridge(new int[] {rc[0],rc[1]}, now_dir, blen);
                    Temp+=blen;
                    Search(new int[] {rc[0],rc[1]},now_dir+1);
                    resetBridge(new int[] {rc[0],rc[1]}, now_dir, blen);
                    Temp-=blen;
//                    다리 설치 안하고 넘어갔을 때
                    Search(new int[] {rc[0],rc[1]},now_dir+1);
                }
//                설치 불가능한 경우
                else {
                    Search(new int[] {rc[0],rc[1]},now_dir+1);
                }
            }
            else {
//            다음 섬 찾아서
                Search(new int[] {rc[0],rc[1]+1},0);
            }
        }
//        섬 구역 아니면
        else {
//            다음탐색
            Search(new int[] {rc[0],rc[1]+1},0);
        }
    }

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/baekjoon/17472.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        v_map = new int[N][M];
        h_map = new int[N][M];

        isize=0;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j]==1)isize++;
            }
        }

        Temp=0;
        Search(new int[] {0,0},0);

//        h_map[3] = new int[]{0,0,1,1,1,1,0,0};
//        v_map[2][3] = 1;
//        v_map[3][3] = 1;
//        v_map[4][3] = 1;
//        v_map[5][3] = 1;
//        
//        is_connected();
//        
//        temp_isize=0;
//        visit = new boolean[N][M];
//        DFS(new int[] {2,0},0);
//        DFS(new int[] {0,3},0)

        if(Ans==Integer.MAX_VALUE)Ans=-1;

        System.out.println(Ans);
//        초기화
        Ans=0;
    }
}

아쉬운점

너무 아쉽다. 머리로 생각은 했었는데, 수직 수평다리 구분하는걸 꼼꼼하게 하지 못해서 망함.

• 시간 (3시간 더걸림)

• 다리 설치 가능한지 체크할 때(is_settable())

  • 이미 설치된 경우 체크할 때 수직다리 체크중에 수평다리 놓아져있으면 설치못하는걸로 판정됨. 반대도 똑같음.
  • now_dir에 따라서 v_map과 h_map을 분리시켜서 고려해줘야함.

• 다리 설치할 때

  • 한 구역에 설치가 끝나면 다음 구역으로 넘어가도록 짰었음.
  • 한 구역에 최대 4개의 다리가 설치될 수 있기 때문에 DFS재귀식 조정했었음.
    • now_dir 변수 추가해서 해결

• 연결성 검사 DFS로 할 때

  1. 수직다리와 수평다리가 겹치는 경우
     • 수직다리로 탐색하다가 수평다리로 넘어가는 경우
     • 역
  2. 수직다리에서 수평으로 섬으로 넘어가는 경우
  3. 수평다리에서 수직으로 섬으로 넘어가는 경우
     • 현재 위치가 수직인지 수평인지만 체크하는 경우에는 교차해서 넘어갈 수 있었음.
     • 위의 경우 모두 now_dir을 함께 고려하면 구분하면서 해결할 수 있었음
  • 다리도 visit 처리하면 다리 걸칠 경우에는 DFS할 수 없음, 다리는 visit 처리 하지말기.
    • 대신 now_dir을 사용해서 방향 고정시켰음.

• 시간초과인가? 다시 풀어봐야겠다

잘한점

• O(N) = N*M맵에 가로로 N개 세로로 M개의 다리 설치 가능* 다리길이 * 연결성 확인 = (2^N * 2^M) * 10 * DFS = 2^10 * 2^10 * 10 * DFS = 10^9 = 시간 안터짐 근데 애매하긴함 - 백트래킹해서 그나마 나은듯
• 최소값 구하는 문제라 재귀 돌리면서 백트래킹해줌
• 다리를 직접 설치할 지, 아니면 다리말고 그냥 순간이동해주는 포탈을 만들어 줄 지 생각했었는데, 포탈의 경우는 양방향으로 포탈을 만들어 줘야하기 때문에 그냥 다리 설치해서 DFS돌리기로 했음.
• 다리 설치를 우선으로 하는 DFS일 수록 Ans더 빨리 찾을 수 있고, 백트래킹을 좀더 빨리 할 수 있다.

다리 설치를 우선하는 DFS vs 다리 미설치를 우선하는 DFS 비교

• 다리 설치가 가능한지 체크, 다리 설치하고, 원상복구하는 메서드 잘만듬.
• 문제 조건 제대로 읽었음.
  • 다리길이 2이상인경우만 고려했었음.
  • 답없는 경우는 Ans=-1;
• 수직다리, 수평다리 map을 각각 만들어서 처리해주기로 했음
  • 여기서 세세한 부분을 신경 안써서 망하긴 했지만.

다른 풀이

• 다리 설치를 할 수 있는지 체크한 후에 그래프처럼 인접노드 만든 후에 DFS돌릴수도 있을듯
• 섬마다 번호 붙인 뒤에