[Softeer]GINI야 도와줘

※소프티어 문제를 풀면서 의식의 흐름을 일기처럼 작성한 글로, 제출한 답안에 대한 설명은 아닙니다.

 

https://softeer.ai/practice/6271

Softeer - 현대자동차그룹 SW인재확보플랫폼

위 문제는 현재까지 참가자가 208명(이제 나포함)인데 정답률이 20% 언저리라 긴장하면서 문제를 봤다.

 

그런데 이문제도 역시 백준에서 많이 본 문제이다.

나는 개인적으로 이런 BFS 중 간단한 문제를 좋아한다..

BFS인데 어지럽고 복잡한 문제는 싫어하지만...

 

비슷한 문제로 호수 어쩌고 문제가 있었던거 같아서 열심히 찾아봤다.

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

위 문제인데..  [백준][3197][백조의호수]... 

백준 백조의 호수 문제가 훠얼씬 복잡해보인다.

 

백준 문제의 경우는 호수물이 점점 사라지는거고,

소프티어 문제는 소나기가 범람하니까 둘이 반대의 경우가 되겠네..  

 

자세히 보니 백조의 호수가 훨씬 더 어려운 문제이다.

GINI는 집은 움직이지 않는 상태에서 태광이가 1번에 1칸씩만 움직이는데

백조들은 둘다 움직이면서 둘이 연결이 가능한 순간을 찾아야 한다....

이런 복잡한 문제보다 GINI 문제가 훨씬 더 반갑고 좋다..

 

소프티어에서 GINI한테 길찾아달라는 문제는,

소나기 구간을 Queue에 먼저 담고,  세차장을 제일 나중에 담았다.

소나기구간을 먼저 넓히고 세차장에서 출발을 나중에 한다면,

시간순서대로 소나기가 길을 먼저 장악하고 그 다음에 태범이가 갈수 있는 길을 찾을 수 있다.

 

정답률이 너무 낮아서 좀 고민하면서 문제를 제출했는데,

정답!

 

이렇게 풀어본 문제들만 나오면 정말 좋겠다..^^

 

import java.io.*;
import java.util.*;

public class Main {

    static class Pair{
        int x, y;
        int type; //0-소나기, 1-길
        Pair(int x, int y, int type){
            this.x = x;
            this.y = y;
            this.type = type;
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        char[][] a = new char[n][m];
        int homX = -1, homY = -1;
        int startX = -1, startY = -1;
        boolean[][] passed = new boolean[n][m];
        Queue<Pair> q = new LinkedList<>();
        for(int i=0; i<n; i++){
            a[i] = br.readLine().toCharArray();
            for(int j=0; j<m; j++){
                if(a[i][j] == 'H'){
                    homX = i;
                    homY = j;
                }else if(a[i][j] == '*'){
                    q.add(new Pair(i,j, 0));
                    passed[i][j] = true;
                }else if(a[i][j] == 'W'){
                    startX = i;
                    startY = j;
                    passed[i][j] = true;
                }
            }
        }

        q.add(new Pair(startX, startY, 1));

        int[][] d = new int[n][m];
        int[] dx = {-1,0,0,1};
        int[] dy = {0,-1,1,0};

        while(!q.isEmpty()){
            Pair p = q.poll();
            for(int k=0; k<4; k++){
                int nx = p.x + dx[k];
                int ny = p.y + dy[k];
                if(nx<0 || nx>=n || ny<0 || ny>=m || a[nx][ny]=='X' || passed[nx][ny]) continue;
                if(p.type == 0){
                    if(a[nx][ny] != 'H'){
                        a[nx][ny] = '*';
                        q.add(new Pair(nx,ny,0));
                        passed[nx][ny] = true;
                    }
                }else{
                    d[nx][ny] = d[p.x][p.y] + 1;
                    q.add(new Pair(nx,ny,1));
                    passed[nx][ny] = true;
                }
            }
        }

        if(d[homX][homY] == 0){
            bw.write("FAIL");
        }else{
            bw.write(String.valueOf(d[homX][homY]));
        }
        bw.close();
    }

}