[Java] bfs 실버모음4

 

 

 

11123 양 한마리... 양 두마리...(실버2)

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

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 rowStep[] = {-1, 0, +1, 0};
  static int colStep[] = {0, -1, 0, 1};
  static char field[][];
  static int height;
  static int width;

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

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

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

      //====계산====//
      for (int i =0; i < height; i++) {
        for (int j =0; j < width; j++) {
          if (field[i][j] == '#') {
            field[i][j] = '.';
            bfs(new Location(i, j));
            result += 1;
          }
        }
      }

      System.out.println(result);
    }
  }

  public static void bfs(Location location) {
    Queue<Location> queue = new LinkedList<>();
    queue.add(location);

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

      for (int i=0; i<rowStep.length; i++) {
        int tempRow = l.r + rowStep[i];
        int tempCol = l.c + colStep[i];

        if (tempRow < height && tempRow >= 0 && tempCol >= 0 && tempCol < width && field[tempRow][tempCol] == '#') {
          field[tempRow][tempCol] = '.';
          queue.add(new Location(tempRow, tempCol));
        }
      }
    }
  }

  static class Location {
    int r; int c;

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

• 상하좌우를 rowStep이랑 colStep에 저장해서 중복코드를 줄여봤다

 

11724 연결 요소의 개수(실버2)

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

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 hasLine[][];
  static boolean visited[];
  static int N;

  public static void main(String[] args) throws Exception {
    //====입력받기====//
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(bf.readLine());
    N = Integer.parseInt(st.nextToken()); //정점의 개수
    int M = Integer.parseInt(st.nextToken()); //간선의 개수

    Queue<Integer> queue = new LinkedList<>();
    visited = new boolean[N];
    hasLine = new boolean[N][N];
    int result = 0;

    for (int i =0; i<M; i++) {
      st = new StringTokenizer(bf.readLine());
      int u = Integer.parseInt(st.nextToken()) - 1;
      int v = Integer.parseInt(st.nextToken()) - 1;
      hasLine[u][v] = true;
      hasLine[v][u] = true;
    }

    //====hasLine 돌면서 연결요소 찾기====//
    for (int i =0; i<N; i++) {
      if (visited[i])
        continue;

      for (int j =0; j<N; j++) {
        if (hasLine[i][j] && !visited[j]) {
          queue.add(j);
          visited[j] = true;
        }
      }

      if (!queue.isEmpty())
        bfs(queue);

      result ++;
    }

    System.out.println(result);
  }

  private static void bfs(Queue<Integer> queue) {
    while (!queue.isEmpty()) {
      int tmp = queue.poll();

      for (int i = 0; i<N; i++) {
        if (visited[i])
          continue;

        if (hasLine[tmp][i]) {
          queue.add(i);
          visited[i] = true;
        }
      }
    }
  }
}

• visited 사용하여 시간을 줄임
• 한 행을 돌면서 연결된 노드를 큐에 담고 bfs 수행

 

11725 트리의 부모 찾기(실버2)

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
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));
    StringTokenizer st;
    Queue<Integer> queue = new LinkedList<>();
    int N = Integer.parseInt(bf.readLine());
    int myParent[] = new int[N+1];

    ArrayList<Integer>[] arr = new ArrayList[N+1];
    for (int i = 0; i<N+1; i++)
      arr[i] = new ArrayList<Integer>();
    
    for (int i =0; i<N-1; i++) {
      st = new StringTokenizer(bf.readLine());
      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());

      arr[a].add(b);
      arr[b].add(a);
    }
    //===========입력 끝===========//
    
    queue.add(1);
    while(!queue.isEmpty()) {
      int tmp = queue.poll();

      for (int i =0; i<arr[tmp].size(); i++) {
        int tmp2 = arr[tmp].get(i);
        if (myParent[tmp2] == 0) {
          myParent[tmp2] = tmp;
          queue.add(tmp2);
        }
      }
    }
    
    //=======결과 출력========//
    for (int i =2; i<myParent.length; i++) 
      System.out.println(myParent[i]);
    
  }
}

• 노드 개수만큼의 크기를 가지는 배열 arr
• arr의 각각의 요소는 자신과 연결된 노드(Integer)의 ArrayList를 가지는 구조로 만듦
• bfs사용, 각 노드들은 자신의 부모를 myParent 배열에 저장함. 값이 0이면 부모가 없는 상태(아직 visit 안한 상태)
• 트리니까 사이클 없음 = visit 배열 필요 x /  myParent의 값으로 visit 여부를 확인함

 

13565 침투(실버2)

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

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

public class Main {
  static int[][] arr;
  static int rowNum;
  static int colNum;
  static int rowMove[] = {1, 0, 0,-1}; //하 좌 우 상
  static int colMove[] = {0,-1,1, 0};

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

    rowNum = Integer.parseInt(st.nextToken());
    colNum = Integer.parseInt(st.nextToken());

    arr = new int[rowNum][colNum];

    for (int i=0; i<rowNum; i++) {
      String line = bf.readLine();
      for (int j=0; j<colNum; j++) {
        arr[i][j] = Character.getNumericValue(line.charAt(j));
      }
    }
    //===========입력 끝===========//

    for (int i=0; i<colNum; i++) {
      if (arr[0][i] == 0) {
        arr[0][i] =1;
        isFinished = dfs(new Location(0, i));
        if (isFinished) {
          System.out.println("YES");
          return;
        }
      }
    }

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

  static boolean dfs(Location loc) {
    int row = loc.row;
    int col = loc.col;

    if (row == rowNum-1)
      return true;

    for (int i =0; i<4; i++) {
      if (row + rowMove[i] >=0 && row + rowMove[i] < rowNum && col + colMove[i] >=0 && col + colMove[i] < colNum) {
        if (arr[row + rowMove[i]][col+colMove[i]] == 0) {
          arr[row + rowMove[i]][col+colMove[i]] = 1;

          boolean isFinished = dfs(new Location(row + rowMove[i], col + colMove[i]));
          if (isFinished)
            return true;
        }
      }
    }

    return false;
  }

  static class Location {
    int row, col;
    public Location(int row, int col) { this.row = row; this.col = col; }
  }
}

• dfs 사용
• 상하좌우를 rowMove, colMove에 저장하여 중복코드를 줄임
  (하좌우상으로 시간을 좀 줄임)

 

1. 0행을 돌면서 만약 0일 경우(전류가 통할 경우) dfs를 수행함
2. dfs의 반환값은 boolean임. 마지막 row에 도착했을 경우 true를 return함. 반환값이 true일 겨우 프로그램 종료
3. dfs에서는 상하좌우를 돌면서 0인지 확인하고 dfs를 수행

 

 

 

파이썬하다가 자바로 넘어오니까 입력받는 코드가 엄청 긴 것 같다.

주요 알고리즘 코드보다 입력받는 코드가 더 긴듯