문제
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);
}
}
}
}
}시행착오
- 풀 면서 자신이 했던 시행착오들
참고자료
- 함께 보면 좋은 글, 링크 등.