[JAVA] ์ฝ๋ฉ ํ
์คํธ ๋๋น ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํ์ด
BFS์ ์๊ฐ๋ณต์ก๋, ๊ณต๊ฐ๋ณต์ก๋ ํ์ธ
BFS๋ 1๋ฒ์ฉ๋ง ๋ฐฉ๋ฌธํ๋ฏ๋ก ์๋ฅผ๋ค์ด rxcxh์ ๋ฐฐ์ด์ ๋ํด BFS๋ฅผ ์ํํ๋ฉด ์๊ฐ๋ณต์ก๋, ๊ณต๊ฐ๋ณต์ก๋ ๋ชจ๋ RxCxH์
๋๋ค (๊ณต๊ฐ๋ณต์ก๋ ์์๋ ์ ๋งํผ์ ์ ์ฅํ ๋ฐฐ์ด์ด ํ์ํ๊ธฐ๋๋ฌธ)
BFS์์๋ 1๋ฒ์ฉ๋ง ๋ฐฉ๋ฌธํ๋๋ก ํ์ ์ ์ง์ด๋ฃ๋๊ฒ์ด ์ค์(์ค๋ณต๋ ๊ฐ์ด ์ฌ๋ฌ๋ฒ ๋ค์ด๊ฐ๋ฉด ์๊ฐ์ด๊ณผ์ ๊ฐ์ ๋ค์ํ ๋ฌธ์ ๊ฐ ์๊น)
2206 ๋ฒฝ๋ถ์๊ธฐ์์ visitedํ๋๋ง ์์ผ๋ฉด ์๋๋์ด์
์๋ฅผ ๋ค์ด ๋ฒฝ์ ์ผ์ฐ ๋ถ์๊ณ ์ด์ ์ ๋ฐฉ๋ฌธํ์ง ์์ ์
์ ํต๊ณผํ๋ฉด ๋ ๋นจ๋ฆฌ ๋์ฐฉํ๋ ๊ฒฝ๋ก๊ฐ ์์ ์ ์๊ณ ,
์ผ๋ถ ์
์ ๋จผ์ ๋ฐฉ๋ฌธํ ๋ค์ ๋ฒฝ์ ๋ถ์๋ฉด ๋ ๋นจ๋ฆฌ ๋์ฐฉํ๋ ๊ฒฝ๋ก๊ฐ ์์ ์ ์๋ค.
ํ๋์ visit[][]๋ง ์ฌ์ฉํ ๊ฒฝ์ฐ ์ํ๋ฅผ ๋ฎ์ด์ฐ๊ณ ํ๋์ ์ ์ฌ์ ๊ฒฝ๋ก๋ฅผ ์์ ์ ์๋ค.
ํฐ์์ ๋๋จธ์ง๋ฅผ ์
๋ ฅํ์ธ์
์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ๋ฅผ ํธ๋ ๊ณผ์ ์์ ๊ฒฐ๊ณผ ๊ฐ์ด ๋งค์ฐ ํฐ ๊ฒฝ์ฐ, ๊ฒฐ๊ณผ ๊ฐ์ ๋๋จธ์ง๋ฅผ ๊ตฌํ๋ผ๋ ๋ฌธ์ ๊ฐ ์์ฃผ ๋ฑ์ฅํ๋ค.
๋จ์ํ ๊ฒฐ๊ณผ ๊ฐ์ ๋ชจ๋๋ฌ ์ฐ์ฐ์ ์ํํ ์ ์ด๋ฏธ ๊ฒฐ๊ณผ ๊ฐ์ ๋๋ฌด ์ปค์ ธ์ ์ค๋ฒํ๋ก์ฐ๊ฐ ๋ฐ์ํ ๊ฒฝ์ฐ๊ฐ ๋๋ถ๋ถ์ด๊ธฐ ๋๋ฌธ์, ์ฐ์ฐ ๊ณผ์ ๋์ค์ ๋ชจ๋๋ฌ ์ฐ์ฐ์ ์ ์ฉํด์ผ ํ๋ค.
์ฐ์ฐ ๊ณผ์ ๋์ค์ ๋ชจ๋๋ฌ ์ฐ์ฐ์ ์ ์ฉํ๋ ค๋ฉด ๋ชจ๋๋ฌ ์ฐ์ฐ์ ๋ถ๋ฐฐ๋ฒ์น์ ๋ํด ์์์ผ ํ๋ค.
๊ฐ ํผ์ฐ์ฐ์์ ๋ชจ๋๋ฌ ์ฐ์ฐ์ ์ทจํ ํ, ๊ณ์ฐ ๊ฒฐ๊ณผ์ ๋ํด ๋ค์ํ๋ฒ ๋ชจ๋๋ฌ ์ฐ์ฐ์ ์ทจํ๋ฉด ๋๋ค. ๋ํ, ๋บ์
์ ๊ฒฝ์ฐ ์์๊ฐ ๋์ค๋ ๊ฒ์ ๋ฐฉ์งํ๊ธฐ ์ํด divisor๋ฅผ ํ๋ฒ ๋ํด์ค๋ค.
(A + B) % p = ((A % p) + (B % p)) % p
(A * B) % p = ((A % p) * (B % p)) % p
(A - B) % p = ((A % p) - (B % p) + p) % p
BufferedWriter์ฌ์ฉํ์ฌ o(n^2)์ ์ถ๋ ฅ ์ํํ๊ธฐ
for (int i = n -1 ; i >= 0 ; i --) {
for (int j = 2 *n -2 ; j >= 0 ; j --) {
bw .write (result [i ][j ]+"" );
}
bw .write ("\n " );
}
bw .flush ();
bw .close ();
StringBuilder + System.out.println() ์ฌ์ฉํด์ ์ถ๋ ฅ ์ํํ๊ธฐ
StringBuilder sb = new StringBuilder ();
for (int i = n -1 ; i >= 0 ; i --) {
for (int j = 2 *n -2 ; j >= 0 ; j --) {
sb .append (result [i ][j ]);
}
sb .append ('\n' );
}
System .out .println (sb );
๋ฉ๋ชจ๋ฆฌ์ ์๊ฐ ๋น๊ต(์ถ๋ ฅ๋ถ๋ถ๋ง ๋ณ๊ฒฝํ๊ฒ์)