[Java] bfs 실버 모음1

 

1388 바닥장식 [실버4]

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

 

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 height = Integer.parseInt(st.nextToken());
    int width = Integer.parseInt(st.nextToken());

    char arr[][] = new char[height][width];

    for (int i =0; i<height; i++) {
      String tmp = bf.readLine();
      for (int j =0; j<width; j++) {
        arr[i][j] = tmp.charAt(j);
      }
    }

    int result = 0;

    for (int i =0; i<height; i++) {
      for (int j =0; j<width; j++) {
        char shape = arr[i][j];
        if (shape == '|') {
          result += 1;
          int a = i+1;
          while (a < height) {
            if (arr[a][j] != '|'){
              break;
            }
            arr[a][j] = ' ';
            a ++;
          }
        } else if (shape == '-'){
          result += 1;
          int b = j+1;
          while (b < width) {
            if (arr[i][b] != '-'){
              break;
            }
            arr[i][b] = ' ';
            b ++;
          }
        }
      }
    }

    System.out.println(result);
  }
}

 

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

public class Main {

  static int height, width;
  static char arr[][];
  static boolean visit[][];

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

    arr = new char[height][width];
    visit = new boolean[height][width];
    int result = 0;

    //arr 2차원 배열 채우기
    for (int i =0; i<height; i++) {
      String tmp = bf.readLine();
      for (int j =0; j<width; j++) {
        arr[i][j] = tmp.charAt(j);
      }
    }

    for (int i =0; i<height; i++) {
      for (int j =0; j<width; j++) {
        if (!visit[i][j]) {
          char shape = arr[i][j];
          if (shape == '|') {
            bfs(i, j, "vertical");
          } else {
            bfs(i, j, "horizontal");
          }
          result ++;
        }
      }
    }
    System.out.println(result);
  }

  private static void bfs(int i, int j, String orient) {
    if (orient == "vertical") {
      int a = i+1;
      while (a < height) {
        if (arr[a][j] != '|'){
          break;
        }
        visit[a][j] = true;
        a ++;
      }
    } else {
      int b = j+1;
      while (b < width) {
        if (arr[i][b] != '-'){
          break;
        }
        visit[i][b] = true;
        b ++;
      }
    }
  }
}

 

함수로 묶어낸 버전

 

 

16173 점프왕 쩰리 (Small) [실버4]

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

 

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

public class Main {
  static int N;
  static int[][] arr;
  static boolean[][] visit;

  static class Point {
    int x, y;

    public Point(int x, int y) {
      this.x = x;
      this.y = y;
    }
  }

  public static void main(String[] args) throws Exception {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    Stack<Point> stack = new Stack<>();
    N = Integer.parseInt(bf.readLine());
    arr = new int[N][N];
    visit = new boolean[N][N];

    //2차원 배열에 입력받기
    for (int i = 0; i< N; i++) {
      st = new StringTokenizer(bf.readLine());
      for (int j =0; j<N; j++) {
        arr[i][j] = Integer.parseInt(st.nextToken());
      }
    }

    stack.push(new Point(0,0));

    while (stack.size() != 0) {
      Point tmp = stack.peek();
      visit[tmp.x][tmp.y] = true;
      int jump = arr[tmp.x][tmp.y];

      if (jump == -1) { //목적지 도착
        System.out.println("HaruHaru");
        return;
      }

      if (tmp.x + jump < N  && !visit[tmp.x + jump][tmp.y]){
        stack.push(new Point(tmp.x + jump, tmp.y));
      } else if (tmp.y + jump < N  && !visit[tmp.x][tmp.y + jump]){
        stack.push(new Point(tmp.x, tmp.y + jump));
      } else {
        stack.pop();
      }
    }

    System.out.println("Hing");
  }
}

 

지나간 한 줄기의 경로를 stack에 저장함.

bfs 함수를 계속 호출하니까 시간초과, 메모리 초과 발생.

 

 

2606 바이러스 [실버3]

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

 

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

public class Main {
  static boolean[][] hasNet;
  static boolean[] infect;
  static int result;
  static int comNum;

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

    hasNet = new boolean[comNum][comNum];
    infect = new boolean[comNum];
    result = 0;

    for (int i=0; i<netNum; i++) {
      StringTokenizer st = new StringTokenizer(bf.readLine());
      int x = Integer.parseInt(st.nextToken()) - 1;
      int y = Integer.parseInt(st.nextToken()) - 1;

      hasNet[x][y] = true; hasNet[y][x] = true;
    }

    find(0);
    System.out.println(result-1);
  }

  static void find(int x) {
    infect[x] = true;
    result++;

    for (int i = 1; i<comNum; i++) {
      if (!infect[i] && hasNet[x][i])
        find(i);
    }
  }
}

 

• 이미 탐색한 경우 infect[n] = true
• infect[n]이 false이고 hasnet이 true인 경우 해당 컴퓨터 n 탐색