아영
- 코드
package Baekjoon.java.silver;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class boj1743 {
static int N,M,K,maxCnt,cnt;
static boolean[][] isChecked,map;
static int[] dr = new int[]{0,0,-1,1};
static int[] dc = new int[]{-1,1,0,0};
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
Queue<int[]> queue = new LinkedList<>();
map = new boolean[N+1][M+1];
isChecked = new boolean[N+1][M+1];
maxCnt = 0;
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
map[a][b] = true;
queue.add(new int[]{a,b});
}
while(!queue.isEmpty()){
int[] now = queue.poll();
if(!isChecked[now[0]][now[1]]){
cnt=1;
dfs(now);
if(maxCnt< cnt) maxCnt = cnt;
}
}
System.out.println(maxCnt);
}
private static void dfs(int[] now){
isChecked[now[0]][now[1]]=true;
for (int i = 0; i < 4; i++) {
int nr = now[0]+dr[i];
int nc = now[1]+dc[i];
if(isRange(nr,nc)&&map[nr][nc]&&!isChecked[nr][nc]){
cnt+=1;
dfs(new int[]{nr,nc});
}
}
}
private static boolean isRange(int n, int m){
return n>=0&&n<=N&&m>=0&&m<=M;
}
}
- 시간,메모리
은영
- 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class baekjoon1743 {
static int ans, cnt;
static int N,M,K;
static int[][] map;
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));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
map = new int[N+1][M+1];
for(int i=0;i<K;i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
map[a][b] = 1;
}
for(int i=1;i<=N;i++) {
for(int j=1;j<=M;j++) {
if(map[i][j]==1) {
cnt = 0;
dfs(i, j);
ans = Math.max(ans, cnt);
}
}
}
System.out.println(ans);
}
public static void dfs(int x, int y) {
map[x][y] = 0;
cnt++;
for(int k=0;k<4;k++ ) {
int nowx = x+dx[k];
int nowy = y+dy[k];
if((1<=nowx&&nowx<n+1)&&(1<=nowy&&nowy<m+1)&&(map[nowx][nowy]==1)) {
dfs(nowx, nowy);
}
}
}
}
- 시간,메모리
건
- 코드
package day_0614;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class BOJ1743 {
static int n, m, k, answer;
static boolean[][] map;
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));
StringTokenizer stk = new StringTokenizer(br.readLine());
n = Integer.parseInt(stk.nextToken());
m = Integer.parseInt(stk.nextToken());
k = Integer.parseInt(stk.nextToken());
map = new boolean[n][m];
for (int i = 0; i < k; i++) {
stk = new StringTokenizer(br.readLine());
map[Integer.parseInt(stk.nextToken()) - 1][Integer.parseInt(stk.nextToken()) - 1] = true;
}
bfs();
System.out.println(answer);
}
static void bfs() {
boolean[][] visit = new boolean[n][m];
Queue<Point> q = new LinkedList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j]) {
visit = new boolean[n][m];
int count = 1;
q.add(new Point(i,j));
visit[i][j] = true;
int x = 0, y = 0, ax = 0, ay = 0;
while(!q.isEmpty()) {
x = q.peek().x;
y = q.peek().y;
q.poll();
for (int k = 0; k < 4; k++) {
ax = x + dx[k];
ay = y + dy[k];
if (ax >= 0 && ay >= 0 && ax < n && ay < n
&& !visit[ax][ay] && map[ax][ay]) {
visit[ax][ay] = true;
q.add(new Point(ax,ay));
count++;
}
}
}
if (count > answer) {
answer = count;
}
}
}
}
}
}
class Point {
public int x, y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
- 시간,메모리
용문
- 코드
class BJ1743 {
private var N = 0
private var M = 0
private var foodPoints: [(r: Int, c: Int)] = []
private var map = [[String]]()
private var visited = [[Bool]]()
private var answer = -1
private let dr = [1, -1, 0, 0]
private let dc = [0, 0, -1, 1]
func solve() {
readComponents()
calc()
printAnswer()
}
private func readComponents() {
let temp = readLine()!.split(separator: " ").map { Int($0)! }
self.N = temp[0]
self.M = temp[1]
let K = temp[2]
map = .init(repeating: .init(repeating: ".", count: M + 1), count: N + 1)
visited = .init(repeating: .init(repeating: false, count: M + 1), count: N + 1)
for _ in 0..<K {
let point = readLine()!.split(separator: " ").map { Int($0)! }
foodPoints.append((point[0], point[1]))
map[point[0]][point[1]] = "#"
}
}
private func calc() {
for point in foodPoints {
if !visited[point.r][point.c] {
answer = max(answer, bfs(from: point))
}
}
}
private func bfs(from: (r: Int, c: Int)) -> Int {
var count = 1
var queue: [(r: Int, c: Int)] = []
queue.append(from)
visited[from.r][from.c] = true
while !queue.isEmpty {
let now = queue.remove(at: 0)
for index in 0..<4 {
let nr = now.r + dr[index]
let nc = now.c + dc[index]
if boundCheck(r: nr, c: nc), !visited[nr][nc], map[nr][nc] == "#" {
visited[nr][nc] = true
count += 1
queue.append((nr, nc))
}
}
}
return count
}
private func boundCheck(r: Int, c: Int) -> Bool {
if r <= 0 || r > N || c <= 0 || c > M { return false }
return true
}
private func printAnswer() {
print(answer)
}
}
BJ1743().solve()
- 시간,메모리
