[Java] bfs 실버모음3

1326 폴짝폴짝

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

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
  static int stoneNum;
  static int stone[];
  static int count[];

  public static void main(String[] args) throws Exception {
    //====입력받기====//
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    stoneNum = Integer.parseInt(bf.readLine());

    if (stoneNum == 1) {
      System.out.println("0");
      return;
    }
    stone = new int[stoneNum];
    count = new int[stoneNum];

    StringTokenizer st = new StringTokenizer(bf.readLine());
    for (int i = 0; i< stoneNum; i++) {
      stone[i] = Integer.parseInt(st.nextToken());
      count[i] = -1;
    }

    st = new StringTokenizer(bf.readLine());
    int start = Integer.parseInt(st.nextToken());
    int end = Integer.parseInt(st.nextToken());
    count[start-1] = 0;

    //====dfs수행====//
    dfs(start-1);

    System.out.println((count[end-1] != 0)?count[end-1]:"-1");
  }

  static void dfs(int index) {
    int jump = stone[index];

    int i =1;
    while (index + jump * i < stoneNum) {

      if (count[index]+1 < count[index + jump*i] || count[index + jump*i] == -1 ) {
        count[index + jump*i] = count[index]+1;
        dfs(index + jump*i);
      }

      i++;
    }

    i = -1;
    while (index + jump*i >= 0) {
      if (count[index]+1 < count[index + jump*i] || count[index + jump*i] == -1) {
        count[index + jump*i] = count[index]+1;
        dfs(index + jump*i);
      }
      i--;
    }
  }
}

 

• stone 배열에 돌 숫자 입력받기
• count 배열에 돌마다 최소 점프 횟수 기록
  • 처음엔 모두 -1로 초기화
• 처음 위치에서 dfs 수행
  • 양의 배수의 경우 모두 구해서 dfs, count의 원래값보다 작을 때만 count 배열을 갱신 
  • 음의 배수 경우 모두 구해서 dfs.
• 마지막엔 목표위치의 count값을 출력,
  • -1이면 도착 못한거고
  • 값이 있으면 해당 값이 최솟값

 

 

2644 촌수계산

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

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int peopleNum = Integer.parseInt(bf.readLine());
    StringTokenizer st = new StringTokenizer(bf.readLine());
    int p1 = Integer.parseInt(st.nextToken());
    int p2 = Integer.parseInt(st.nextToken());
    int linkNum = Integer.parseInt(bf.readLine());
    
    boolean links[][] = new boolean[peopleNum+1][peopleNum+1];
    int chon[] = new int[peopleNum+1];
    Arrays.fill(chon, -1);

    for (int i =0; i<linkNum; i++) {
      st = new StringTokenizer(bf.readLine());
      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());
      links[a][b] = true;
      links[b][a] = true;
    }

    Queue<Integer> queue = new LinkedList<>();
    queue.add(p1);
    chon[p1] = 0;

    while (!queue.isEmpty()) {
      int tmp = queue.poll();
      
      for (int i = 1; i<peopleNum+1; i++) {
        if (chon[i] == -1 && links[tmp][i]) {
          queue.add(i);
          chon[i] = chon[tmp] + 1;
        }
      }
    }
    
    System.out.println((chon[p2] != -1)? chon[p2] : -1);
  }
}

 

chon에 촌수를 적어가면서 구함

 

 

4963 섬의 개수

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

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
  static Queue<Location> queue = new LinkedList<>();;
  static int width;
  static int height;
  static int map[][];

  public static void main(String[] args) throws Exception {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int result;
    while (true) {
      StringTokenizer st = new StringTokenizer(bf.readLine());
      width = Integer.parseInt(st.nextToken());
      height = Integer.parseInt(st.nextToken());
      result = 0;

      if (width ==0)
        break;

      map = new int[height][width];

      for (int i =0; i<height; i++) {
        st = new StringTokenizer(bf.readLine());
        for (int j=0; j<width; j++) {
          map[i][j] = Integer.parseInt(st.nextToken());
        }
      }

      for (int i =0; i<height; i++) {
        for (int j=0; j<width; j++) {
          if (map[i][j] == 1) {
            map[i][j] = 0;
            queue.add(new Location(i, j));
            bfs();

            result += 1;
          }
        }
      }

      System.out.println(result);
    }
  }

  static void bfs() {
    while (!queue.isEmpty()) {
      Location tmp = queue.poll();

      if (tmp.r+1 < height) {
        if (map[tmp.r+1][tmp.c] == 1) {
          map[tmp.r+1][tmp.c] = 0;
          queue.add(new Location(tmp.r+1, tmp.c));
        }

        if (tmp.c +1< width && map[tmp.r+1][tmp.c+1] == 1) {
          map[tmp.r+1][tmp.c+1] = 0;
          queue.add(new Location(tmp.r+1, tmp.c+1));
        }

        if (tmp.c -1 >= 0 && map[tmp.r+1][tmp.c-1] == 1) {
          map[tmp.r+1][tmp.c-1] = 0;
          queue.add(new Location(tmp.r+1, tmp.c-1));
        }
      }

      if (tmp.r-1 >= 0) {
        if (map[tmp.r-1][tmp.c] == 1) {
          map[tmp.r-1][tmp.c] = 0;
          queue.add(new Location(tmp.r-1, tmp.c));
        }

        if (tmp.c +1< width && map[tmp.r-1][tmp.c+1] == 1) {
          map[tmp.r-1][tmp.c+1] = 0;
          queue.add(new Location(tmp.r-1, tmp.c+1));
        }

        if (tmp.c -1 >= 0 && map[tmp.r-1][tmp.c-1] == 1) {
          map[tmp.r-1][tmp.c-1] = 0;
          queue.add(new Location(tmp.r-1, tmp.c-1));
        }
      }

      if (tmp.c -1 >= 0 && map[tmp.r][tmp.c-1] == 1) {
        map[tmp.r][tmp.c-1] = 0;
        queue.add(new Location(tmp.r, tmp.c-1));
      }
      if (tmp.c +1< width &&map[tmp.r][tmp.c+1] == 1) {
        map[tmp.r][tmp.c+1] = 0;
        queue.add(new Location(tmp.r, tmp.c+1));
      }
    }
  }

  static class Location {
    int r;
    int c;

    public Location(int r, int c) {
      this.r = r;
      this.c = c;
    }
  }
}

 

• 노가다 한 문제 ㅠㅠ 

 

 

 

조금 더 줄인 코드

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
  static int width;
  static int height;
  static int map[][];
  
  static int dh[] = {-1,-1, -1, 0, 0, +1, +1, +1};
  static int dw[] = {-1, 0, 1, -1, 1, -1, 0, 1};

  public static void main(String[] args) throws Exception {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

    while (true) {
      StringTokenizer st = new StringTokenizer(bf.readLine());
      width = Integer.parseInt(st.nextToken());
      height = Integer.parseInt(st.nextToken());
      int result = 0;

      if (width ==0)
        break;

      map = new int[height][width];

      for (int i =0; i<height; i++) {
        st = new StringTokenizer(bf.readLine());
        for (int j=0; j<width; j++) {
          map[i][j] = Integer.parseInt(st.nextToken());
        }
      }

      for (int i =0; i<height; i++) {
        for (int j=0; j<width; j++) {
          if (map[i][j] == 1) {
            bfs(new Location(i, j));
            result += 1;
          }
        }
      }
      System.out.println(result);
    }
  }

  static void bfs(Location loc) {
    Queue<Location> queue = new LinkedList<>();;
    
    queue.add(loc);
    map[loc.r][loc.c] = 0;

    while (!queue.isEmpty()) {
      Location tmp = queue.poll();

      for (int i =0; i<8; i++) {
        int tmpR = tmp.r + dh[i];
        int tmpC = tmp.c + dw[i];

        if (tmpR <height && tmpC <width && tmpR >= 0 && tmpC >=0) {
          if (map[tmpR][tmpC] == 1) {
            map[tmpR][tmpC] = 0;
            queue.add(new Location(tmpR, tmpC));
          }
        }
      }
    }
  }

  static class Location {
    int r;
    int c;

    public Location(int r, int c) {
      this.r = r;
      this.c = c;
    }
  }
}

 

• 좌상, 상, 우상, 우, 우하, 하, 좌하, 좌 8가지 방향으로 bfs를 해야하는 경우, 인덱스를 만들어놓으면 편하다는 걸 알아냈다.
• 코드길이가 훨씬 줄어들고 오타낼 확률도 줄어듦
• 이거 외엔 그냥 bfs문제다.

 

11060 점프 점프

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

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
  static int mazeSize;
  static int maze[];
  static int count[];

  public static void main(String[] args) throws Exception {
    //====입력받기====//
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    mazeSize = Integer.parseInt(bf.readLine());

    if (mazeSize == 1) {
      System.out.println("0");
      return;
    }

    maze = new int[mazeSize];
    count = new int[mazeSize];

    StringTokenizer st = new StringTokenizer(bf.readLine());

    for (int i =0; i<mazeSize; i++) {
      maze[i] = Integer.parseInt(st.nextToken());
      count[i] = 0;
    }
    maze[mazeSize-1] = 0;

    //====dfs수행====//
    dfs(0);

    System.out.println((count[mazeSize-1] != 0)?count[mazeSize-1]:"-1");
  }

  static void dfs(int index) {
    int jump = maze[index];

    for (int i =0; i<jump; i++) {
      if (index + (i+1) < mazeSize) {
        if (count[index]+1 < count[index+i+1] || count[index+i+1] == 0) {
          count[index+i+1] = count[index]+1;
          dfs(index + (i + 1));
        }
      }
    }
  }
}

 

• dfs로 구함
• 될 수 있는 경우의 수들 전부 dfs함
• count로 각 칸으로 갈 수 있는 최소 점프 수를 기입하여 경우의 수를 조금 줄임
• size가 1일 때 처리 해줌(이거 때문에 첫 트 때 틀림 ㅜㅜ)