[Java] 백준 14496 그대, 그머가 되어 - 실버2

 

 

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

14496번: 그대, 그머가 되어

 

 

연결리스트 사용 bfs 풀이

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

public class Main {
  public static void main(String[] args) throws IOException {
    //입력 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] starr = br.readLine().split(" ");
    int start = Integer.parseInt(starr[0]);
    int end = Integer.parseInt(starr[1]);

    starr = br.readLine().split(" ");
    int charCnt = Integer.parseInt(starr[0]);
    int pairCnt = Integer.parseInt(starr[1]);

    Map<Integer, List<Integer>> map = new HashMap<>();
    for (int i =0; i<pairCnt; i++) {
      starr = br.readLine().split(" ");
      int a = Integer.parseInt(starr[0]);
      int b = Integer.parseInt(starr[1]);

      //기존에 데이터 있으면
      if (map.get(a) != null) {
        List<Integer> tmp = map.get(a);
        tmp.add(b);
      } else {
        List<Integer> tmp = new ArrayList<>();
        tmp.add(b);
        map.put(a, tmp);
      }

      //기존에 데이터 있으면
      if (map.get(b) != null) {
        List<Integer> tmp = map.get(b);
        tmp.add(a);
      } else {
        List<Integer> tmp = new ArrayList<>();
        tmp.add(a);
        map.put(b, tmp);
      }
    }
    //입력 끝 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

    boolean[] visit = new boolean[charCnt+1];

    Queue<List<Integer>> queue = new LinkedList<>();
    List<Integer> tmp = new ArrayList<>();
    tmp.add(start); tmp.add(0);
    queue.add(tmp);
    visit[start] = true;

    int result = -1;
    while(!queue.isEmpty()) {
      List<Integer> list = queue.poll();
      int value = list.get(0);
      int moveCnt = list.get(1);

      if (value == end) {
        result = moveCnt;
        break;
      }

      if (map.get(value) != null) {
        List<Integer> canChange = map.get(value);

        for (Integer c: canChange) {
          if (visit[c] == false) {
            visit[c] = true;
            tmp = new ArrayList<>();
            tmp.add(c); tmp.add(moveCnt+1);
            queue.add(tmp);
          }
        }
      }
    }

    System.out.println(result);
  }
}

• 연결리스트 방식으로 그래프를 저장해야 시간초과가 나지 않는다
• 최소 횟수이므로, 적은 횟수부터 큐에 들어가는 방식인 bfs가 맞다
• visit배열을 (숫자 개수 + 1) 크기로 만들어주어 index로 접근한다
• 큐를 만들어 시작점을 넣어준다. 큐에는 값과 이동횟수를 같이 넣어준다
• 큐가 빌 때까지 반복한다
  • 이동가능한 숫자들에 대해(canchange)
  • visit가 false

 

 

 

 

좀 더 가독성 있는 풀이

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

public class Main {
  public static void main(String[] args) throws IOException {
    //입력 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] starr = br.readLine().split(" ");
    int start = Integer.parseInt(starr[0]);
    int end = Integer.parseInt(starr[1]);

    starr = br.readLine().split(" ");
    int charCnt = Integer.parseInt(starr[0]);
    int pairCnt = Integer.parseInt(starr[1]);

    Map<Integer, List<Integer>> map = new HashMap<>();

    //init map
    for (int i =1; i<charCnt+1; i++)
      map.put(i, new ArrayList<>());

    for (int i =0; i<pairCnt; i++) {
      starr = br.readLine().split(" ");
      int a = Integer.parseInt(starr[0]);
      int b = Integer.parseInt(starr[1]);

      List<Integer> tmpA = map.get(a);
      tmpA.add(b);

      List<Integer> tmpB = map.get(b);
      tmpB.add(a);
    }
    //입력 끝 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

    boolean[] visit = new boolean[charCnt+1];

    Queue<List<Integer>> queue = new LinkedList<>();
    List<Integer> tmp = new ArrayList<>();
    tmp.add(start); tmp.add(0);
    queue.add(tmp);
    visit[start] = true;

    int result = -1;
    while(!queue.isEmpty()) {
      List<Integer> list = queue.poll();
      int value = list.get(0);
      int moveCnt = list.get(1);

      if (value == end) {
        result = moveCnt;
        break;
      }

      List<Integer> canChange = map.get(value);
      for (Integer c: canChange) {
        if (visit[c] == false) {
          visit[c] = true;
          tmp = new ArrayList<>();
          tmp.add(c); tmp.add(moveCnt+1);
          queue.add(tmp);
        }
      }
    }

    System.out.println(result);
  }
}

 

 

 

 

 

+) 배열방식 사용(시간초과 남)

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

public class Main {
  public static void main(String[] args) throws IOException {
    //입력 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] starr = br.readLine().split(" ");
    int start = Integer.parseInt(starr[0]);
    int end = Integer.parseInt(starr[1]);

    starr = br.readLine().split(" ");
    int charCnt = Integer.parseInt(starr[0]);
    int pairCnt = Integer.parseInt(starr[1]);

    boolean[][] arr = new boolean[charCnt+1][charCnt+1];
    for (int i =0; i<pairCnt; i++) {
      starr = br.readLine().split(" ");
      int a = Integer.parseInt(starr[0]);
      int b = Integer.parseInt(starr[1]);

      arr[a][b] = true;
      arr[b][a] = true;
    }
    //입력 끝 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

    boolean[] visit = new boolean[charCnt+1];

    Queue<List<Integer>> queue = new LinkedList<>();
    List<Integer> tmp = new ArrayList<>();
    tmp.add(start); tmp.add(0);
    queue.add(tmp);
    visit[start] = true;

    int result = -1;
    while(!queue.isEmpty()) {
      List<Integer> list = queue.poll();
      int value = list.get(0);
      int moveCnt = list.get(1);

      if (value == end) {
        result = moveCnt;
        break;
      }

      for (int i=1; i<charCnt+1; i++) {
        if (visit[i] == false && arr[value][i] == true) {
          tmp = new ArrayList<>();
          tmp.add(i); tmp.add(moveCnt + 1);
          queue.add(tmp);
          visit[value] = true;
        }
      }
    }

    System.out.println(result);
  }
}

 

 

 

계속 시간 초과하는 배열방식