[伯俊]2012号オーガニック白菜/Java,Python
Baekjoon Online Judge
algorithm practice
-問題を逐次解く
24.DFSとBFS
グラフを巡るアルゴリズムを学びましょう.
Java/Python
4.有機白菜
1012号
白菜の位置問題
この問題は白菜畑に必要な白菜の白ミミズを探す問題です.
dfs(int x,int y):
1.現在のノードにアクセスします.
2.現在のノードから上、下、左、右のノードに移動できることを確認します.(可能であれば、dfs()を呼び出して、範囲外であるかどうか、白菜が存在するかどうかを決定します.)
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static boolean[][] arr;
static boolean[][] check; // 방문 여부
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
int result;
for(int i = 0; i < T; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
int cnt = Integer.parseInt(st.nextToken());
arr = new boolean[N][M];
check = new boolean[N][M];
result = 0;
for(int j = 0; j < cnt; j++){
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
arr[y][x] = true;
}
for(int j = 0; j < N; j++){
for(int k = 0; k < M; k++){
if(checkLocation(j, k)){
result++;
dfs(j, k);
}
}
}
bw.write(result + "\n");
}
bw.flush();
bw.close();
br.close();
}
public static boolean checkLocation(int row, int col){
// 좌표 값이 잘못된 경우
if(row < 0 || row >= N || col < 0 || col >= M) return false;
// 이미 지나간 경로인 경우 || 집이 아닌 경우
if(check[row][col] || !arr[row][col]) return false;
return true;
}
public static void dfs(int x, int y){
check[x][y] = true;
// '상'의 좌표
if(checkLocation(x - 1, y)) dfs(x - 1, y);
// '하'의 좌표
if(checkLocation(x + 1, y)) dfs(x + 1, y);
// '좌'의 좌표
if(checkLocation(x, y - 1)) dfs(x, y - 1);
// '우'의 좌표
if(checkLocation(x, y + 1)) dfs(x, y + 1);
}
}
import sys
sys.setrecursionlimit(10000)
T = int(sys.stdin.readline())
def dfs(x, y):
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
# 상,하,좌,우 확인
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if (0 <= nx < N) and (0 <= ny < M):
if arr[nx][ny] == 1:
arr[nx][ny] = -1
dfs(nx, ny)
for _ in range(T):
M, N, K = map(int, sys.stdin.readline().split())
arr = [[0]*M for _ in range(N)]
cnt = 0
# 행렬 생성
for _ in range(K):
a, b = map(int, sys.stdin.readline().split())
arr[b][a] = 1
for i in range(N): # 행 (바깥)
for j in range(M): # 열 (내부)
if arr[i][j] > 0:
dfs(i, j)
cnt += 1
print(cnt)
Reference
この問題について([伯俊]2012号オーガニック白菜/Java,Python), 我々は、より多くの情報をここで見つけました https://velog.io/@jini_eun/백준-1012번-유기농-배추-Java-Pythonテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol