์ฝ๋ ๋๋ฌด ๋๋ฌ์์ dfs ์ฌ์ฉํด์ ํ์ด๋ดค๋๋ฐ ํ๋ฆฌ๊ณ ๋์ ๊ถ๊ธ์
package baekjoon.bruteforce._14500
import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
lateinit var numbers: Array<IntArray>
lateinit var isVisited: Array<BooleanArray>
val ans = TreeSet<Int>()
val delta = ArrayList<ArrayList<Pair<Int, Int>>>()
fun main() {
val bf = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.out))
var st = StringTokenizer(bf.readLine()) // ์
๋ ฅ๋ฐ๊ธฐ
val rawi = st.nextToken().toInt() // i
val rawj = st.nextToken().toInt() // j
numbers = Array(rawi) { IntArray(rawj) } // ์ซ์ ์ ์ฅํ ๋ฐฐ์ด
isVisited = Array(rawi) { BooleanArray(rawj) } // ๋ฐฉ๋ฌธํ๋์ง ์ ์ฅํ ๋ฐฐ์ด(์๊ธฐ ์์ ๋๋ฒ ์ฐธ์กฐํ๋ฉด ๊ฐ ๋ปฅํ๊ธฐ๋จ)
for (i in 0 until rawi) {
st = StringTokenizer(bf.readLine())
for (j in 0 until rawj) {
numbers[i][j] = st.nextToken().toInt() // ๋ฐฐ์ด์ ๊ฐ ์ ์ฅ
}
}
tmino() // t๋ฏธ๋
ธ ๋ชจ์ ์ธํ
for (i in 0 until rawi) {
for (j in 0 until rawj) {
calculate(i, j) // t๋ฏธ๋
ธ ๊ณ์ฐ
for (k in isVisited){
k.fill(false) // ๋ฐฉ๋ฌธ๋ฐฐ์ด ์ด๊ธฐํ
}
isVisited[i][j] = true // ์ฒซ๋
ธ๋ ๋ฐฉ๋ฌธ ์ฒดํฌ
dfs(i, j, 1, numbers[i][j]) // dfs ์คํ
}
}
bw.write("${ans.last()}\n") // ๊ฐ ํ์(treeset ๊ฐ์ฅ ํฐ๊ฐ)
bw.flush()
}
fun dfs(i: Int, j: Int, count: Int, sum: Int) {
if (count == 4) { // 4๊ฐ์ผ๋
ans.add(sum) // ํฉ ํธ๋ฆฌ์
์ ์ถ๊ฐ
return // dfs ๋ ๋๋ฌ ์ข
๋ฃ
}
val dx = arrayOf(0, 0, 1, -1) // ๋ธํ๊ฐ ๊ฐ๋ก
val dy = arrayOf(1, -1, 0, 0) // ๋ธํ๊ฐ ์ธ๋ก
for (n in 0..3) {
val newi = dy[n] + i
val newj = dx[n] + j
if (newi < 0 || newi >= numbers.size) continue // ์ธ๋ก ๊ฐ ์ ํจ์ฒดํฌ
if (newj < 0 || newj >= numbers[newi].size) continue // ๊ฐ๋ก ๊ฐ ์ ํจ์ฒดํฌ
if (isVisited[newi][newj]) continue // ๋ฐฉ๋ฌธํ์๋์ง ์ฒดํฌ
isVisited[newi][newj] = true
dfs(newi, newj, count + 1, sum + numbers[newi][newj])
}
}
fun tmino() {
delta.add(ArrayList())
delta.last().add(Pair(0, 0))
delta.last().add(Pair(0, 1))
delta.last().add(Pair(-1, 0))
delta.last().add(Pair(1, 0))
delta.add(ArrayList())
delta.last().add(Pair(0, 0))
delta.last().add(Pair(0, -1))
delta.last().add(Pair(-1, 0))
delta.last().add(Pair(1, 0))
delta.add(ArrayList())
delta.last().add(Pair(0, 0))
delta.last().add(Pair(0, -1))
delta.last().add(Pair(-1, 0))
delta.last().add(Pair(0, 1))
delta.add(ArrayList())
delta.last().add(Pair(0, 0))
delta.last().add(Pair(0, -1))
delta.last().add(Pair(1, 0))
delta.last().add(Pair(0, 1))
}
fun calculate(i: Int, j: Int) {
for (arrs in delta) {
var sum = 0
for (d in arrs) {
val newi = d.first + i
val newj = d.second + j
if (newi < 0 || newi >= numbers.size) break
if (newj < 0 || newj >= numbers[newi].size) break
sum += numbers[newi][newj]
}
ans.add(sum)
}
}
t๋ฏธ๋
ธ ์ ์ธํ๊ณ ๋๋จธ์ง๋ฅผ dfs๋ก ๋ฐ๊ฟ๋ดค๋๋ฐ...
4 4
5 1 1 5
2 1 1 2
2 1 1 2
1 1 1 1