[Java] bfs 실버모음2

25418 정수 a를 k로 만들기 [실버3]

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

 

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

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

    int A = Integer.parseInt(st.nextToken());
    int K = Integer.parseInt(st.nextToken());
    int result = 0;

    while (A != K) {
      result ++;
      K = (K%2 == 0 && K/2 >= A)? K/2 : K-1;
    }

    System.out.println(result);
  }
}

 

• K 기준으로 계산
• K가 짝수면 2를 나눠주고/ K가 홀수면 1을 빼줌
• 반복하여 연산 횟수를 result 저장

 

1012 유기농 배추 [실버2]

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

 

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

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

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

    for (int t =0; t<T; t++) {
      StringTokenizer st = new StringTokenizer(bf.readLine());
      width = Integer.parseInt(st.nextToken());
      height = Integer.parseInt(st.nextToken());
      int K = Integer.parseInt(st.nextToken());
      field = new boolean[height][width];
      result = 0;

      //배추밭 채우기
      for (int i =0 ; i< K; i++) {
        st = new StringTokenizer(bf.readLine());
        int c = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());
        field[r][c] = true;
      }

      //모든 인덱스 돌아가면서 확인
      for (int i =0; i< height; i++) {
        for (int j =0; j<width; j++) {
          if (field[i][j]) {
            result += 1;
            field[i][j] = false;
            queue.add(new Location(i, j));
            bfs();
          }
        }
      }

      System.out.println(result);
    }
  }

  static void bfs() {
    while (!queue.isEmpty()) {
      Location l = queue.poll();
      if (l.r-1>=0 && field[l.r-1][l.c]) {  //왼
        queue.add(new Location(l.r-1,l.c));
        field[l.r-1][l.c] = false;
      }
      if (l.r+1<height && field[l.r+1][l.c]) { //오
        queue.add(new Location(l.r+1,l.c));
        field[l.r+1][l.c] = false;
      }
      if (l.c -1 >= 0 && field[l.r][l.c - 1]) { //위
        queue.add(new Location(l.r, l.c - 1));
        field[l.r][l.c - 1] = false;
      }
      if (l.c + 1 < width && field[l.r][l.c + 1]) { //아래
        queue.add(new Location(l.r, l.c + 1));
        field[l.r][l.c + 1] = false;
      }
    }
  }

  static class Location {
    int r;
    int c;

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

 

• 행열과 좌표가 헷갈렸던 문제. 
• 좌표값을 그냥 행열값으로 통일해서 풀었다.

 

1260 DFS와 BFS [실버2]

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

 

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

public class Main {
  static boolean links[][];
  static boolean bfsVisit[];
  static boolean dfsVisit[];
  static String bfsResult = "";
  static String dfsResult = "";
  static int nodeNum;

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

    nodeNum = Integer.parseInt(st.nextToken());
    int linkNum = Integer.parseInt(st.nextToken());
    int start = Integer.parseInt(st.nextToken());

    links = new boolean[nodeNum+1][nodeNum+1];
    bfsVisit = new boolean[nodeNum+1];
    dfsVisit = new boolean[nodeNum+1];

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

    dfs(start);
    bfs(start);

    System.out.println(dfsResult.trim());
    System.out.println(bfsResult.trim());
  }

  static void dfs(int x) {
    dfsVisit[x] = true;

    dfsResult += (" " + x);
    for (int i =1; i<nodeNum+1; i++) {
      if (!dfsVisit[i] && links[x][i]) {
        dfs(i);
      }
    }
  }

  static void bfs(int x) {
    Queue<Integer> queue = new LinkedList<>();
    queue.add(x);
    bfsVisit[x] = true;

    while (!queue.isEmpty()) {
      int tmp = queue.poll();
      bfsResult += (" " + tmp);
      for (int i =1; i<nodeNum+1; i++) {
        if (!bfsVisit[i] && links[tmp][i]) {
          queue.add(i);
          bfsVisit[i] = true;
        }
      }
    }
  }
}