[Java] 백준 14496 그대, 그머가 되어

알고리즘/백준

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

fladi 2023. 7. 15. 06:04

728x90

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

14496번: 그대, 그머가 되어

첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000) 이후 M개의 줄에 걸쳐 치환 가능한 문

www.acmicpc.net

연결리스트 사용 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);
  }
}

728x90