글 읽기 - 미로찾기 BFS 메모리초과가 나옵니다 ㅠㅠ

sdh9615 2년 전 0

현재 이코드로 제출하면 메모리초과가 나옵니다

제가 실수한건가 싶어 정답코드를 봤는데 어떤차이인지 잘 모르겠습니다 ㅠㅠ

(수정)

visited를 체크하는부분을 바꿨더니 해결됬는데

왜 해결됬는지는 잘 모르겠습니다 이유가 있을까요?

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*

private val br = BufferedReader(InputStreamReader(System.`in`))
private val bw = BufferedWriter(OutputStreamWriter(System.`out`))

// n x m 의 크기를 받는코드
private val st = StringTokenizer(br.readLine())
private val n = st.nextToken().toInt()
private val m = st.nextToken().toInt()

// BFS 에서 활용할 GRAPH, Visited
private val list : Array<IntArray> = Array(n){IntArray(m)}
private val visited = Array(n){BooleanArray(m)}

private fun main() {

    // Graph 값 넣어줌
    repeat(n) { idx ->
        val line = br.readLine().map{it.digitToInt()}.toIntArray()
        list[idx] = line
    }

    bfs()
    bw.write("${list[n-1][m-1]}")
    bw.flush()
    bw.close()
    br.close()
}

private fun bfs() {
    // 4방향으로 확인
    val dx = intArrayOf(1, 0, -1, 0)
    val dy = intArrayOf(0, 1, 0, -1)

    // BFS 에서 활용할 Queue, 최초시작점 0,0 offer
    val queue = LinkedList<Pair<Int, Int>>()
    queue.offer(Pair(0, 0))

    while (queue.isNotEmpty()) {
        // queue 에서 꺼냄
        val temp = queue.poll()!!

        // x, y 값
        val tempX = temp.first
        val tempY = temp.second

        // (오류) -> 기존에 체크하던 위치
        // visited[tempX][tempY] = true

        // 4방향 움직임
        for (i in 0 until 4) {
            val x2 = tempX + dx[i]
            val y2 = tempY + dy[i]

            // 그래프 범위밖이거나 이미 방문했거나 0인부분은 생략
            if (x2 !in 0 until n || y2 !in 0 until m) continue
            if(list[x2][y2] == 0 || visited[x2][y2]) continue

            // 위의 조건을 통과하면 해당좌표를 넣어주고, +1해줌
            queue.offer(Pair(x2,y2))
            list[x2][y2] = list[tempX][tempY] + 1
            
            // (해결) -> visited 체크위치 바꾼곳
            visited[x2][y2] = true
        }
    }
}

zenith82114 2년 전 4

방문 표시를 큐에서 꺼낼 때가 아니라 넣을 때 해주어야 같은 좌표가 큐에 여러 번 들어가는 일을 방지할 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

미로찾기 BFS 메모리초과가 나옵니다 ㅠㅠ

sdh9615 2년 전 0

zenith82114 2년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말