๐ ๋ฌธ์
https://www.acmicpc.net/problem/7576
๋ฌธ์
์ฒ ์์ ํ ๋งํ ๋์ฅ์์๋ ํ ๋งํ ๋ฅผ ๋ณด๊ดํ๋ ํฐ ์ฐฝ๊ณ ๋ฅผ ๊ฐ์ง๊ณ ์๋ค. ํ ๋งํ ๋ ์๋์ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ๊ฒฉ์ ๋ชจ์ ์์์ ์นธ์ ํ๋์ฉ ๋ฃ์ด์ ์ฐฝ๊ณ ์ ๋ณด๊ดํ๋ค.
์ฐฝ๊ณ ์ ๋ณด๊ด๋๋ ํ ๋งํ ๋ค ์ค์๋ ์ ์ต์ ๊ฒ๋ ์์ง๋ง, ์์ง ์ต์ง ์์ ํ ๋งํ ๋ค๋ ์์ ์ ์๋ค. ๋ณด๊ด ํ ํ๋ฃจ๊ฐ ์ง๋๋ฉด, ์ต์ ํ ๋งํ ๋ค์ ์ธ์ ํ ๊ณณ์ ์๋ ์ต์ง ์์ ํ ๋งํ ๋ค์ ์ต์ ํ ๋งํ ์ ์ํฅ์ ๋ฐ์ ์ต๊ฒ ๋๋ค. ํ๋์ ํ ๋งํ ์ ์ธ์ ํ ๊ณณ์ ์ผ์ชฝ, ์ค๋ฅธ์ชฝ, ์, ๋ค ๋ค ๋ฐฉํฅ์ ์๋ ํ ๋งํ ๋ฅผ ์๋ฏธํ๋ค. ๋๊ฐ์ ๋ฐฉํฅ์ ์๋ ํ ๋งํ ๋ค์๊ฒ๋ ์ํฅ์ ์ฃผ์ง ๋ชปํ๋ฉฐ, ํ ๋งํ ๊ฐ ํผ์ ์ ์ ๋ก ์ต๋ ๊ฒฝ์ฐ๋ ์๋ค๊ณ ๊ฐ์ ํ๋ค. ์ฒ ์๋ ์ฐฝ๊ณ ์ ๋ณด๊ด๋ ํ ๋งํ ๋ค์ด ๋ฉฐ์น ์ด ์ง๋๋ฉด ๋ค ์ต๊ฒ ๋๋์ง, ๊ทธ ์ต์ ์ผ์๋ฅผ ์๊ณ ์ถ์ด ํ๋ค.
ํ ๋งํ ๋ฅผ ์ฐฝ๊ณ ์ ๋ณด๊ดํ๋ ๊ฒฉ์๋ชจ์์ ์์๋ค์ ํฌ๊ธฐ์ ์ต์ ํ ๋งํ ๋ค๊ณผ ์ต์ง ์์ ํ ๋งํ ๋ค์ ์ ๋ณด๊ฐ ์ฃผ์ด์ก์ ๋, ๋ฉฐ์น ์ด ์ง๋๋ฉด ํ ๋งํ ๋ค์ด ๋ชจ๋ ์ต๋์ง, ๊ทธ ์ต์ ์ผ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ๋ผ. ๋จ, ์์์ ์ผ๋ถ ์นธ์๋ ํ ๋งํ ๊ฐ ๋ค์ด์์ง ์์ ์๋ ์๋ค.
์ ๋ ฅ
์ฒซ ์ค์๋ ์์์ ํฌ๊ธฐ๋ฅผ ๋ํ๋ด๋ ๋ ์ ์ M,N์ด ์ฃผ์ด์ง๋ค. M์ ์์์ ๊ฐ๋ก ์นธ์ ์, N์ ์์์ ์ธ๋ก ์นธ์ ์๋ฅผ ๋ํ๋ธ๋ค. ๋จ, 2 ≤ M,N ≤ 1,000 ์ด๋ค. ๋์งธ ์ค๋ถํฐ๋ ํ๋์ ์์์ ์ ์ฅ๋ ํ ๋งํ ๋ค์ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋ค. ์ฆ, ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์๋ ์์์ ๋ด๊ธด ํ ๋งํ ์ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋ค. ํ๋์ ์ค์๋ ์์ ๊ฐ๋ก์ค์ ๋ค์ด์๋ ํ ๋งํ ์ ์ํ๊ฐ M๊ฐ์ ์ ์๋ก ์ฃผ์ด์ง๋ค. ์ ์ 1์ ์ต์ ํ ๋งํ , ์ ์ 0์ ์ต์ง ์์ ํ ๋งํ , ์ ์ -1์ ํ ๋งํ ๊ฐ ๋ค์ด์์ง ์์ ์นธ์ ๋ํ๋ธ๋ค.
ํ ๋งํ ๊ฐ ํ๋ ์ด์ ์๋ ๊ฒฝ์ฐ๋ง ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
์ฌ๋ฌ๋ถ์ ํ ๋งํ ๊ฐ ๋ชจ๋ ์ต์ ๋๊น์ง์ ์ต์ ๋ ์ง๋ฅผ ์ถ๋ ฅํด์ผ ํ๋ค. ๋ง์ฝ, ์ ์ฅ๋ ๋๋ถํฐ ๋ชจ๋ ํ ๋งํ ๊ฐ ์ต์ด์๋ ์ํ์ด๋ฉด 0์ ์ถ๋ ฅํด์ผ ํ๊ณ , ํ ๋งํ ๊ฐ ๋ชจ๋ ์ต์ง๋ ๋ชปํ๋ ์ํฉ์ด๋ฉด -1์ ์ถ๋ ฅํด์ผ ํ๋ค.
โ๏ธ ํ์ด
๐๏ธ 2021.09.24
๋ ์ด ๋ฌธ์ ์ข ์ ํ์๋ค ์ฐํํ!
์ฒ์ ๊ตฌ์๋ ์ญ์ญ ๋์๊ณ ๊ตฌ์๋๋ก ์ฝ๋ฉ๋ ์ญ์ญ ๋์๋ค. ์ด๋ฐ ๋ ๋ ์์ด์ผ ํ์ฃผ๋ฅผ ์ํ๊ณ ๊ณ์ ์ฝ๋ฉํ์ง.......
ํ์ด๋ BFS๋ก ํ์๋ค.
๋๋๊ฐ ๋ฎ์ ๋งํผ ๊ทธ๋ ๊ฒ ์ด๋ ต์ง ์์ ๋ฌธ์ ๋ผ, ์ง์ด์ผํ ํฌ์ธํธ๋ง ์ ์ง์ผ๋ฉด ๋์๋ค.
1. ์ผ์๋ฅผ ๋จ์๋ก ๊ณ์ฐ ํด์ผํ๋ค. ์ต๋ ํ ๋งํ ๊ฐ ํ ๊ฐ๋ง ์๋ ๊ฒ์ ์๋๋ฏ๋ก, ํ ์ฌ์ด์ฆ(๋น์ผ๊น์ง ์ต์ ํ ๋งํ ์ ์ฒด ๊ฐ์)๋ฅผ ๊ธฐ์ค์ผ๋ก ์ผ์๋ฅผ ์ธ์ด์ผ ํ๋ค. ํ์ ๋จ์์๋ ํ ๋งํ ๊ฐ์๋งํผ ์ฒ๋ฆฌํ๊ณ ๋๋ฉด ๊ทธ ๋ค์ ์ผ์์ ์ฒ๋ฆฌํด์ผํ๋ ํ ๋งํ ๊ฐ ํ์ ์์ด๊ฒ ๋๋ค.
2. ์์ต์ ํ ๋งํ ๊ฐ์๋ฅผ ๋ฏธ๋ฆฌ ์ธ์ด๋ ๋ค์, ํ ๋งํ ๊ฐ ์ต์ ๋๋ง๋ค ๊ฐ์๋ฅผ ์ค์ด๋ ๋ฐฉ์์ผ๋ก ์ต์ง ๋ชปํ ํ ๋งํ ๋ฅผ ์ฒดํฌํ๋ค. ํ ๋งํ ๊ฐ ์๋ ์นธ(-1)์ ๋ง๋ ๊ธธ์ด ๋งํ๋ฉด ๋จ์ด์ ธ ์๋ ํ ๋งํ ๋ ์ตํ ์ ์๊ธฐ ๋๋ฌธ์, ํ๊ฐ ๋น ๋๊น์ง ๊ณ์ฐํ๋ค๊ณ ํด์ ๋์ด ์๋๊ณ ์์ต์ ํ ๋งํ ๊ฐ์๊ฐ 0์ด ๋์๋์ง๋ฅผ ๋ณด์์ผ ํ๋ค. ๋ฐ๋ผ์ ํ๊ฐ ๋น๊ฒ ๋๋ฉด ๋ฐ๋ก ์ ์ ํ ํ ๋งํ ๊ฐ ๋จ์์๋์ง ์ฒดํฌํ๋ ์์ ์ ํด์ค๋ค.
๐โ๏ธ ์๊ฒฌ
2๋ ์ ์ ๋ ๋ฆผ์ผ๋ก ์จ๋ ๋น๊ณต๊ฐ ํฌ์คํธ๋ค์ ์ ๋ฆฌํ๊ณ ์๋๋ฐ... ๋ฌธ์ ๊ฐ ์ค๋ฒ1์์ ๊ณจ๋5๋ก ์ํฅ์กฐ์ ๋๋ค ๐ณ
๋ ์ฉ๋ ํ ๋งํ ์์ ์ต๋ ํ ๋งํ ๋ก ๋ด์ฉ๋ ์ด์ง ๋ฐ๋์๋ค ใ ใ
ํ์ด ์จ๋ ๊ฑธ ๋ณด๋ ์ด๋์ ๋๋ ์์ ๋์ BFS๋ ๊ฝค๋ ์ด๋ ค์ ํ๋ ๊ฒ ๊ฐ์๋ฐ, ํ๊ณ ๋ฟ๋ฏํดํ๋ ๊ณผ๊ฑฐ์ ๋์ฌ..๊ฝค๋ ๊ท์ฌ์ ๊ตฌ๋ง(ใ ใ )
๐ป ์์ค์ฝ๋: ์๋ฐ(Java)
public class Main_๋ฐฑ์ค_7576_ํ ๋งํ _์ค๋ฒI {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
int[][] map = new int[N][M];
int tomatoes = 0;
Queue<int[]> queue = new LinkedList<int[]>();
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if(map[i][j]==1) queue.offer(new int[] {i, j});
if(map[i][j]==0) tomatoes++;
}
}//input
// 1. ์
๋ ฅ๋ฐ์ ๋ 0์ ๊ฐ์(์ ์ต์ ํ ๋งํ ) ์ธ๊ณ , 1์ธ ๊ฒฝ์ฐ ํ์ ๋ฃ์ด์ฃผ๊ธฐ
// 2. ํ์ ์
๋ ฅ๋ ๊ฐ๋ค์ ํ๋์ฉ ๊บผ๋ด์ด ์ฃผ๋ณ ํ ๋งํ ์ตํ๊ณ ํ์ ๋ฃ๊ธฐ. ์ฃผ๋ณ ๊ฐ์ด -1์ด๊ฑฐ๋ 1์ธ ๊ฒฝ์ฐ ํ์ ๋ฃ์ง ์์.
// 3. ํ๊ฐ ๋น๊ณ ๋์ ๋จ์ ์ ์ต์ ํ ๋งํ ๊ฐ์๊ฐ 0์ด ์๋๋ฉด -1
int[] dr = {1, -1, 0, 0};
int[] dc = {0, 0, 1, -1};
int result = 0;
while(tomatoes != 0 && queue.size()>0) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] cur = queue.poll();
int r = cur[0];
int c = cur[1];
for (int j = 0; j < 4; j++) {
int nr = r + dr[j];
int nc = c + dc[j];
if(nr>=0 && nr<N && nc>=0 && nc<M && map[nr][nc]==0) {
tomatoes--;
map[nr][nc]=1;
queue.offer(new int[] {nr,nc});
}
}
}// depth
result ++;
}// end of queue
if(tomatoes != 0) result = -1;
System.out.println(result);
}//end of main
}//end of class
๐ ๐ ๐
๏ผฐ๏ฝ๏ฝ๏ฝ๏ฝ ๏ฝ ๏ผข๏ฝ ๏ผณ๏ผก๏ผน
๐๐ฉ๐ข๐ฏ๐ฌ๐ด ๐ง๐ฐ๐ณ ๐ณ๐ฆ๐ข๐ฅ๐ช๐ฏ๐จ