https://www.acmicpc.net/problem/7576
문제풀이
BFS 문제입니다.
문제 조건에
1. 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다.
라는 조건이 있습니다.
일반적으로 M이 행(세로) 이고 N이 열(가로) 인 경우가 많지만, 이 문제 같은경우 반대로 되어있습니다.이때, 단순하게 N을 먼저 입력받고 똑같이 진행하면 y = x 대칭으로 바뀌게 되어 M이 가로 칸의 수이지만 세로로 변하고, N이 세로 칸의 수이지만 가로로 변하기에 일반 문제랑 똑같이 진행하면 됩니다.
또한 M, N 이 1000 이기에 최대 1000 * 1000 = 1,000,000(백만) 개의 수를 입력받는데 이떄 시간초과가 날 수 있습니다.
일반적으로 1억개의 연산이 진행되어야 1초 초과인데, 입출력같은경우 시간이 더 오래걸리기에 이런 많은 입력을 받을떄는 BufferedReader를 활용하여 진행해야 시간초과가 나지 않습니다.
2. 문제에서 익은 토마토는 1개가 아니라 여러개가 될 수 있다.
저 같은경우 이 조건을 늦게봐서 1개인줄알고 코드를 풀었다가 예제 3번의 예시를 보고 다시 재수정했습니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int M, N, result=0;
public static int[][] map;
public static boolean[][] visited;
public static Queue<Node> q = new LinkedList<>();
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());
map = new int[M][N];
visited = new boolean[M][N];
int startx = 0, starty = 0;
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if(map[i][j] == 1) {
q.offer(new Node(i,j, 0));
startx = i;
starty = j;
}
}
}
BFS();
for(int i=0;i<M;i++) {
for(int j=0;j<N;j++) {
if(map[i][j] == 0) {
System.out.println("-1");
return ;
}
}
}
System.out.println(result);
}
public static void BFS() {
int[] dx = {-1,1,0,0};
int[] dy = {0,0,-1,1};
// visited[startx][starty] = true;
while(!q.isEmpty()) {
Node temp = q.poll();
int x = temp.x;
int y = temp.y;
int time = temp.time;
result = time;
visited[x][y] = true;
for(int dir=0;dir<4;dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if(nx < 0 || nx >= M || ny < 0 || ny >= N ) continue;
if(visited[nx][ny] == true) continue;
if(map[nx][ny] == -1 || map[nx][ny] == 1) continue;
q.offer(new Node(nx, ny, time + 1));
visited[nx][ny] = true;
map[nx][ny] = 1;
}
}
}
}
class Node{
int x;
int y;
int time;
public Node(int x, int y, int time) {
this.x = x;
this.y = y;
this.time = time;
}
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 13549 숨바꼭질 3 - BFS JAVA (0) | 2023.06.20 |
---|---|
[백준] 7569 토마토 - BFS (0) | 2023.06.19 |
[백준] 14940 쉬운 최단거리 - BFS (0) | 2023.06.18 |
[백준] 16918 봄버맨 - BFS (0) | 2023.06.17 |
[백준] 2667 단지번호붙이기 - BFS(넓이우선탐색) JAVA (0) | 2023.06.14 |