알고리즘 5주차

문제

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

• 알고리즘 : DFS
• 난이도 :

접근

• 내가 풀기 위해 접근했던 순서

가정

• 풀기 전에 ~ 식으로 풀면 되겠다. 등.

풀어보기

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  
  
public class Main {  
  
    static int n;  
    static int m;  
    static int garbage;  
    static int count;  
    static boolean[][] visit;  
    static int[][] map;  
    static int max = 0;  
  
    static int dx[] = {-1, 1, 0, 0};  
    static int dy[] = {0, 0, 1, -1};  
  
    public static void main(String[] args) throws IOException {  
  
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
       String str = br.readLine();  
       StringTokenizer st = new StringTokenizer(str);  
       n = Integer.parseInt(st.nextToken());  
       m = Integer.parseInt(st.nextToken());  
       garbage = Integer.parseInt(st.nextToken());  
  
       visit = new boolean[n][m];  
       map = new int[n][m];  
  
       for (int i = 0; i < garbage; i++) {  
          st = new StringTokenizer(br.readLine());  
          int a = Integer.parseInt(st.nextToken()) - 1;  
          int b = Integer.parseInt(st.nextToken()) - 1;  
          map[a][b] = 1;  
  
       }  
  
       for (int i = 0; i < n; i++) {  
          for (int j = 0; j < m; j++) {  
             if (!visit[i][j] && map[i][j] == 1) {  
                DFS(i, j);  
                max = Integer.max(max, count);  
                count = 0;  
  
             }  
          }  
       }  
       System.out.println(max);  
  
    }  
  
    public static void DFS(int x, int y) {  
       visit[x][y] = true;  
       count++;  
  
       for (int i = 0; i < 4; i++) {  
          int nextX = x + dx[i];  
          int nextY = y + dy[i];  
  
          if (nextX >= 0 && nextY >= 0 && nextX < n && nextY < m) {  
             if (!visit[nextX][nextY] && map[nextX][nextY] == 1) {  
                DFS(nextX, nextY);  
             }  
          }  
       }  
  
    }  
}

시행착오

• 풀 면서 자신이 했던 시행착오들

참고자료

• 함께 보면 좋은 글, 링크 등.

문제

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

• 알고리즘 : BFS
• 난이도 :

접근

• 내가 풀기 위해 접근했던 순서

가정

• 풀기 전에 ~ 식으로 풀면 되겠다. 등.

풀어보기

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.ArrayList;  
import java.util.LinkedList;  
import java.util.Queue;  
import java.util.StringTokenizer;  
  
public class Main {  
  
    static int n;  
    static int m;  
    static int[][]  board;  
    static boolean[][] visit;  
    static int[] dx = {-1, 1, 0, 0};  
    static int[] dy = {0, 0, -1, 1};  
  
    static Queue<int[]> queue;  
  
    public static void main(String[] args) throws IOException {  
  
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
       StringTokenizer st = new StringTokenizer(br.readLine());  
       n=Integer.parseInt(st.nextToken());  
       m=Integer.parseInt(st.nextToken());  
  
       board=new int[n][m];  
       visit=new boolean[n][m];  
  
       for(int i=0;i<n;i++){  
           String str= br.readLine();  
           String[] strArr = str.split("");  
  
          for(int j=0;j<m;j++){  
             board[i][j]=Integer.parseInt(strArr[j]);  
          }  
  
       }  
  
       BFS(0,0);  
  
       System.out.println(board[n-1][m-1]);  
  
    }  
  
    public static void BFS(int x,int y) {  
       queue = new LinkedList<>();  
       queue.add(new int[]{x,y});  
  
       while(!queue.isEmpty()){  
          int[] now = queue.poll();  
          int nowX = now[0];  
          int nowY = now[1];  
  
          for(int i=0;i<4;i++){  
             int nextX=nowX+dx[i];  
             int nextY=nowY+dy[i];  
  
             if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m)  
                continue;  
             if (visit[nextX][nextY] || board[nextX][nextY] == 0)  
                continue;  
  
             queue.add(new int[] {nextX, nextY});  
             board[nextX][nextY] = board[nowX][nowY] + 1;  
             visit[nextX][nextY] = true;  
  
  
          }  
  
       }  
  
    }  
  
  
}

시행착오

• 풀 면서 자신이 했던 시행착오들

참고자료

• 함께 보면 좋은 글, 링크 등.

문제

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

• 알고리즘 : ?
• 난이도 :

접근

• 내가 풀기 위해 접근했던 순서

가정

• 풀기 전에 ~ 식으로 풀면 되겠다. 등.

풀어보기

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  
  
public class Main {  
  
    static int n;  
    static int m;  
    static int garbage;  
    static int count;  
    static boolean[][] visit;  
    static int[][] map;  
    static int max = 0;  
  
    static int dx[] = {-1, 1, 0, 0};  
    static int dy[] = {0, 0, 1, -1};  
  
    public static void main(String[] args) throws IOException {  
  
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
       String str = br.readLine();  
       StringTokenizer st = new StringTokenizer(str);  
       n = Integer.parseInt(st.nextToken());  
       m = Integer.parseInt(st.nextToken());  
       garbage = Integer.parseInt(st.nextToken());  
  
       visit = new boolean[n][m];  
       map = new int[n][m];  
  
       for (int i = 0; i < garbage; i++) {  
          st = new StringTokenizer(br.readLine());  
          int a = Integer.parseInt(st.nextToken()) - 1;  
          int b = Integer.parseInt(st.nextToken()) - 1;  
          map[a][b] = 1;  
  
       }  
  
       for (int i = 0; i < n; i++) {  
          for (int j = 0; j < m; j++) {  
             if (!visit[i][j] && map[i][j] == 1) {  
                DFS(i, j);  
                max = Integer.max(max, count);  
                count = 0;  
  
             }  
          }  
       }  
       System.out.println(max);  
  
    }  
  
    public static void DFS(int x, int y) {  
       visit[x][y] = true;  
       count++;  
  
       for (int i = 0; i < 4; i++) {  
          int nextX = x + dx[i];  
          int nextY = y + dy[i];  
  
          if (nextX >= 0 && nextY >= 0 && nextX < n && nextY < m) {  
             if (!visit[nextX][nextY] && map[nextX][nextY] == 1) {  
                DFS(nextX, nextY);  
             }  
          }  
       }  
  
    }  
}

시행착오

• 풀 면서 자신이 했던 시행착오들

참고자료

• 함께 보면 좋은 글, 링크 등.