Closed gyeoul closed 1 year ago
코드 너무 더러워서 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() val rawj = st.nextToken().toInt() 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() for (i in 0 until rawi) { for (j in 0 until rawj) { calculate(i, j) for (k in isVisited){ k.fill(false) } isVisited[i][j] = true dfs(i, j, 1, numbers[i][j]) } } bw.write("${ans.last()}\n") bw.flush() } fun dfs(i: Int, j: Int, count: Int, sum: Int) { if (count == 4) { ans.add(sum) return } 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
답: 12 / 출력: 10 으로 틀려서 생각좀 해봐야될듯.. dfs 값을 5개 받으면 14가 정상적으로 나오는데 4는 왜 12가 안나오고 10만 나올까...
코드 너무 더러워서 dfs 사용해서 풀어보기(틀림)
t미노 제외하고 나머지를 dfs로 바꿔봤는데...
답: 12 / 출력: 10 으로 틀려서 생각좀 해봐야될듯.. dfs 값을 5개 받으면 14가 정상적으로 나오는데 4는 왜 12가 안나오고 10만 나올까...