SWEA[7396] - 종구의 딸이름 짓기[D5]

링크

SWEA[7396]

문제설명

• BFS

문제풀이

• 격자 완전탐색 -> 최적값의 경로만 고려하기 -> BFS

문제코드

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

public class Solution7396_BFS {

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

    public static int N;
    public static int M;
    public static char[][] map;
    public static boolean[][] visited;
    public static LinkedList<int[]> q = new LinkedList<int[]>();


    public static void main(String[] args) throws NumberFormatException, IOException {

        System.setIn(new FileInputStream("res/swea/7396.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {

            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            map = new char[N][M];
            visited = new boolean[N][M];

            for (int i = 0; i < N; i++) {
                map[i]=br.readLine().toCharArray();
            }

            int[] now;
            int qsize;
            int nr;
            int nc;
            StringBuilder ans = new StringBuilder();

            q.add(new int[] {0,0});
            visited[0][0]=true;
            char min=map[0][0];
            char before_min=map[0][0];
            while(!q.isEmpty()) {
                ans.append(min);
                before_min=min;
                qsize= q.size();
                min = Character.MAX_VALUE;
                for (int i = 0; i < qsize; i++) {
                    now = q.poll();
//                    이전에 넣었던 min 보다 큰 q는 무시해야함.
                    if(before_min!=map[now[0]][now[1]]) {
                        continue;
                    }
                    for (int d = 0; d < 2; d++) {
                        nr = now[0] + dir[d][0];
                        nc = now[1] + dir[d][1];
                        if(nr>=0 && nr<N && nc>=0 && nc<M && !visited[nr][nc] && min>=map[nr][nc]) {
                            min=map[nr][nc];
                            q.add(new int[] {nr,nc});
                            visited[nr][nc]=true;
                        }
                    }
                }
            }

            System.out.println("#"+test_case+" "+ans.toString());
//            초기화
            q.clear();
        }
    }
}

아쉬운점

• 이전 단계의 최대값 초기화 위치가 잘못되었음.
• visit 고려하면서 다음칸 탐색해야함.
  • 안하면 중복되면서 경로가 증식됨
  • 시간초과
    • 만약 경로 갯수를 구하라고 하면 visit고려안하고 일단 넣고봐야함.
  • (1,0) ->(1,1) 이랑 (0,1) -> (1,1) 이랑 결국 최소값이 동일한 (1,0), (0,1)에서 출발한거기 때문에 겹치는거 생략가능
• Ans string 길이 MAX 1999 인데 Stringbuilder 쓰는게 빠름

잘한점

• O(N) = 2000^2 = 4*10^6
• BFS로 생각함
• 방법1
  • comp로 다음 큐에있는 애들을 사전순서대로 정렬 후 min만 남기기
  • 0.6s
• 방법2
  • 다음 큐에 넣을 때, min을 구하면서 min이하인경우만 추가함.
  • 그리고 다음에 계산할 때 min이 아닌애들은 무시하면서 BFS
  • 0.25s