์ ๋ฒ ์ฃผ์ ์ตํ ๊ฐ๋ ์ ๋ฐํ์ผ๋ก ์ด๋ฒ์ฃผ์ ํ๋ก๊ทธ๋๋จธ์ค ๋ฌธ์ ๋ฅผ ํ์ด๋ณด์๋ค.
๊ฒ์ ๋งต ์ต๋จ๊ฑฐ๋ฆฌ - ํ๋ก๊ทธ๋๋จธ์ค
๋ฌธ์ ๋ฐ๋ก ๋ณด๋ฌ ๊ฐ๊ธฐ (๋ฌธ์ ์ถ์ฒ : ํ๋ก๊ทธ๋๋จธ์ค )
๋ฌธ์ ์์ ์๊ตฌํ๋ ๊ฒ์ ์๋ ํ ์ง์์ธ maps[n-1][n-1]
์ ๋์ฐฉ ํ๊ธฐ ๊น์ง ์ฌ๋ฌ๊ฐ์ ๊ฒฝ๋ก์ค์๋ ๋ ๋น ๋ฅธ ๊ฒฝ๋ก๋ฅผ ์ฐพ๋ ๊ฒ์ด๋ค. ๊ทธ ๊ฒฝ๋ก์ ํด๋นํ๋ ์นธ์ ๊ฐ์์ธ ์ต์๊ฐ์ ๊ตฌํ๋ ๊ฒ์ด ์ด ๋ฌธ์ ์ ๋ชฉํ์ด๋ค.
BFS๋ ๊ฒฝ๋ก๊ฐ ์ฌ๋ฌ๊ฐ์ผ ๋ ๊ฐ์ฅ ์งง์ ๊ฒฝ๋ก์ ๋์ฐฉ์ ๋ํ ๋ณด์ฅ์ด ๊ฐ๋ฅํ๊ธฐ ๋๋ฌธ์, ์ด ์๋ฆฌ๋ก ์ธํด maps[n-1][n-1]
์ ๊ฐ์ฅ ๋นจ๋ฆฌ ๋์ฐฉํ์ฌ ์ฐ์ฐ ํ๊ฒ ๋๋ฉด ์ต์๊ฐ์ด ๋๋ค.
์ถ๋ฐ ์ง์ ์์ ํน์ ์ง์ ๊น์ง์ ๊ฒฝ๋ก์์ ํด๋นํ๋ ์นธ์ ๊ฐ์๋ฅผ ํธ๋ํน ํ๋ ๋ฐฉ๋ฒ์, ํ์ฌ ์ง์ ์์ ๋ค์ ์ธ์ ๋
ธ๋๋ฅผ, ๋ค์ ๋ชฉํ ์ง์ ์ผ๋ก ๋ฐฉ๋ฌธํ๊ธฐ ์ํด ํ์ ๋ฃ์ ์ ๋ฐฉ๋ฌธ์ ํธ๋ํน ํ๋ ๊ณต๊ฐ์ ์ฌํ๊น์ง ์๋ ๊ฒฝ๋ก
๋ค์ ๋ฐฉ๋ฌธ ์ง์ = ํ์ฌ ์ง์ ์นธ ๊ฐ์ +1
์ ํตํด ์
๋ฐ์ดํธ๋ฅผ ํด์ค๋ค.
/**
* ์ต๋จ ๊ฑฐ๋ฆฌ : BFS ์ฌ์ฉ
* 1. 4๋ฐฉํฅ ํ์
* 2. visited ๋ฐฐ์ด์ ํตํด ๋ฐฉ๋ฌธ ์ง์ ๊น์ง์ ๊ฑฐ๋ฆฌ๋ฅผ ์
๋ฐ์ดํธ ํ๋ค. (์ด์ ๋
ธ๋์ ๊ฑฐ๋ฆฌ + 1)
* 3. queue์๋ ๋ฐฉ๋ฌธํ ๋
ธ๋๋ฅผ ๋ฃ๋๋ค.
* 4. ๋ฐฉ๋ฌธํ ๋
ธ๋๊ฐ ์์๋๊น์ง ๋ฐ๋ณตํ๋ค.
*/
function solution(maps) {
let n = maps[0].length
let m = maps.length
let x = 0,
y = 0
let visited = Array.from({ length: maps.length }, () =>
Array.from({ length: maps[0].length }, () => -1),
)
//๋ถ๋๋จ์
const dx = [0, 1, 0, -1]
const dy = [-1, 0, 1, 0] //๋ถ ๋ ๋จ ์
let queue = [[y, x]]
visited[y][x] = 1
while (queue.length) {
const [y, x] = queue.shift()
for (let i = 0; i < 4; i++) {
let ny = dy[i] + y
let nx = dx[i] + x
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue // ๋ฒ์ ๋ฒ์ด๋๋ฉด continue;
if (maps[ny][nx] === 0) continue // ๋ฒฝ์ด๋ฉด continue
if (visited[ny][nx] !== -1) continue //์ด๋ฏธ ๋ฐฉ๋ฌธํ ๋
ธ๋๋ฉด continue
queue.push([ny, nx]) //๋ฐฉ๋ฌธํ ๋
ธ๋๋ฅผ queue์ ๋ฃ๋๋ค.
visited[ny][nx] = visited[y][x] + 1 //๋ฐฉ๋ฌธ์ฒ๋ฆฌ์ ์ด์ ๋
ธ๋์ ๊ฑฐ๋ฆฌ +1
}
}
return visited[m - 1][n - 1]
}
๋คํธ์ํฌ
๋ฌธ์ ๋ฐ๋ก ๋ณด๋ฌ ๊ฐ๊ธฐ (๋ฌธ์ ์ถ์ฒ : ํ๋ก๊ทธ๋๋จธ์ค )
๋ฌธ์ ์์ ์๋ฃ๊ตฌ์กฐ ํน์ฑ์ ๋ํ ํํธ๋ฅผ ์ป์ ์ ์์ด์ผ ํ๋ค.
๋ฌธ์ : ๋คํธ์ํฌ๋ ์ปดํจํฐ ์ํธ ๊ฐ์ ์ ๋ณด๋ฅผ ๊ตํํ ์ ์๋๋ก ์ฐ๊ฒฐ๋ ํํ๋ฅผ ์๋ฏธํฉ๋๋ค. ์๋ฅผ ๋ค์ด, ์ปดํจํฐ A์ ์ปดํจํฐ B๊ฐ ์ง์ ์ ์ผ๋ก ์ฐ๊ฒฐ๋์ด์๊ณ , ์ปดํจํฐ B์ ์ปดํจํฐ C๊ฐ ์ง์ ์ ์ผ๋ก ์ฐ๊ฒฐ๋์ด ์์ ๋ ์ปดํจํฐ A์ ์ปดํจํฐ C๋ ๊ฐ์ ์ ์ผ๋ก ์ฐ๊ฒฐ๋์ด ์ ๋ณด๋ฅผ ๊ตํํ ์ ์์ต๋๋ค. ๋ฐ๋ผ์ ์ปดํจํฐ A, B, C๋ ๋ชจ๋ ๊ฐ์ ๋คํธ์ํฌ ์์ ์๋ค๊ณ ํ ์ ์์ต๋๋ค. ์ปดํจํฐ์ ๊ฐ์ n, ์ฐ๊ฒฐ์ ๋ํ ์ ๋ณด๊ฐ ๋ด๊ธด 2์ฐจ์ ๋ฐฐ์ด computers๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๋คํธ์ํฌ์ ๊ฐ์๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํ์์ค.
์ฌ๊ธฐ์ A์ C๊ฐ ๊ฐ์ ์ ์ผ๋ก ์ฐ๊ฒฐ๋์ด ์๋ค๋ ์๋ฏธ๋ A-B-C๋ก ์ฐ๊ฒฐ์ด ๋๋ค. ์ด๋ ๊ทธ๋ํ์์ ํธ๋ฆฌ๊ฐ ๊ฐ์ง๋ acyclic ํน์ฑ์ด๋ค.
๋คํธ์ํฌ์ ๊ฐ์๋ ๊ณง ์ปดํจํฐ๊ฐ ์ฐ๊ฒฐ๋ ์งํฉ์ ๊ฐ๋ ์ผ๋ก ๋ณผ ์ ์์ผ๋ฉฐ ์ด๋ ๊ณง ์งํฉ์ด ์ฌ๋ฌ๊ฐ๊ฐ ๋ ์ ์์์ ์๋ฏธ ํ๋ค.
์ด๋ฐ ํน์ฑ์ผ๋ก ๋ฏธ๋ฃจ์ด ๋ณด์ BFS๋ณด๋ค๋ DFS๋ฅผ ํตํด ์ฐ๊ฒฐ๋ ๋ชจ๋ ์ปดํจํฐ๋ฅผ ํ์ํ๊ณ ๋๊ธฐ๋ฉด ๋ค๋ฅธ ์ง์ ์์ ๋ค์ ์ฐ๊ฒฐ๋ ์ปดํจํฐ๋ฅผ ํ์ํ๋ ๊ณผ์ ์ ๊ฑฐ์ณ์ผ ํ๋ค.
ํ์์ ์ํด ์ฃผ์ด์ง ์ธ์ ํ๋ ฌ์์ ์ด๋ป๊ฒ ํ์์ ํ ๊ฒ์ธ๊ฐ๋ ์ค์ํ๋ค. computers[i][j] = 1์ด๋ฉด ์ฐ๊ฒฐ ๋์๋ค๊ณ ํ์ผ๋, index ๊ฐ๋ ์ผ๋ก 0๋ฒ ์ปดํจํฐ์ ์ฐ๊ฒฐ๋ ์ด 3๊ฐ์ ์ปดํจํฐ๊ฐ ์๋ค๋ ๊ฑธ ์๊ฒ ๋๋ค.
;[
[1, 1, 0], //i=0 , 0๋ฒ ์ปดํจํฐ์ ์ธ์ ์ปดํจํฐ๋ค
[1, 1, 0], //i=1 , 1๋ฒ ์ปดํจํฐ์ ์ธ์ ์ปดํจํฐ๋ค
[0, 0, 1], // i=2 , 2๋ฒ ์ปดํจํฐ์ ์ธ์ ์ปดํจํฐ๋ค
]
๋๊ธด ์ง์ ์์ ๋ค์ ์ฐ๊ฒฐ๋ ์ปดํจํฐ๋ฅผ ์ฐพ๋ ๋ฐฉ๋ฒ์ visited ๊ณต๊ฐ์ ํตํด ์ด๋ฏธ ํ์ํ๋ ์ปดํจํฐ๋ ํ์ํ์ง ์๋๋ค.
if (!visited[i]) {
dfs(i)
cnt += 1
}
ํ์ด
function solution(n, computers) {
const visited = Array.from({ length: n }, () => 0)
let cnt = 0
// ๋ชจ๋ ์ปดํจํฐ ์ง์ ์ ๋์์ผ ํจ. ๋๊ธด ๋คํธ์ํฌ์์ ์๋ก์ด ๋คํธ์ํฌ๋ฅผ ํ์ฑํ๊ธฐ ์ํด
for (let i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i)
cnt += 1
}
}
return cnt
function dfs(v) {
visited[v] = 1
;(computers[v] || []).forEach((value, idx) =>
!!value && !visited[idx] ? dfs(idx) : false,
)
}
}
๋ฐฐ๋ฌ
๋ฌธ์ ๋ฐ๋ก ๋ณด๋ฌ ๊ฐ๊ธฐ (๋ฌธ์ ์ถ์ฒ : ํ๋ก๊ทธ๋๋จธ์ค )
๋ฌธ์ ์ง๋ฌธ ์ผ๋ถ N๊ฐ์ ๋ง์๋ก ์ด๋ฃจ์ด์ง ๋๋ผ๊ฐ ์์ต๋๋ค. ์ด ๋๋ผ์ ๊ฐ ๋ง์์๋ 1๋ถํฐ N๊น์ง์ ๋ฒํธ๊ฐ ๊ฐ๊ฐ ํ๋์ฉ ๋ถ์ฌ๋์ด ์์ต๋๋ค. ๊ฐ ๋ง์์ ์๋ฐฉํฅ์ผ๋ก ํตํํ ์ ์๋ ๋๋ก๋ก ์ฐ๊ฒฐ๋์ด ์๋๋ฐ, ์๋ก ๋ค๋ฅธ ๋ง์ ๊ฐ์ ์ด๋ํ ๋๋ ์ด ๋๋ก๋ฅผ ์ง๋์ผ ํฉ๋๋ค. ๋๋ก๋ฅผ ์ง๋ ๋ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ ๋๋ก๋ณ๋ก ๋ค๋ฆ ๋๋ค. ํ์ฌ 1๋ฒ ๋ง์์ ์๋ ์์์ ์์ ๊ฐ ๋ง์๋ก ์์ ๋ฐฐ๋ฌ์ ํ๋ ค๊ณ ํฉ๋๋ค. ๊ฐ ๋ง์๋ก๋ถํฐ ์์ ์ฃผ๋ฌธ์ ๋ฐ์ผ๋ ค๊ณ ํ๋๋ฐ, N๊ฐ์ ๋ง์ ์ค์์ K ์๊ฐ ์ดํ๋ก ๋ฐฐ๋ฌ์ด ๊ฐ๋ฅํ ๋ง์์์๋ง ์ฃผ๋ฌธ์ ๋ฐ์ผ๋ ค๊ณ ํฉ๋๋ค. ๋ง์์ ๊ฐ์ N, ๊ฐ ๋ง์์ ์ฐ๊ฒฐํ๋ ๋๋ก์ ์ ๋ณด road, ์์ ๋ฐฐ๋ฌ์ด ๊ฐ๋ฅํ ์๊ฐ K๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ์์ ์ฃผ๋ฌธ์ ๋ฐ์ ์ ์๋ ๋ง์์ ๊ฐ์๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
๋ฌธ์ ์์ ์๊ตฌํ๋ ๊ฒ์ 1๋ฒ ๋ง์ ๋ถํฐ K ์๊ฐ ์ดํ๋ก ๋ฐฐ๋ฌ ๊ฐ๋ฅํ ๋ง์์ ๊ฐ์๋ฅผ ์ฐพ๋ ๊ฒ์ด๋ค.
๋ง์์ด ์๋ฐฉํฅ์ผ๋ก ํตํ ํ ์ ์๋ ์
์ ํตํด ์๋ฐฉํฅ ๊ทธ๋ํ์์ ์์ ์๋ค. ์ฐ๊ฒฐ๋ ๋ง์์ ์ด๋ํ๋ฉด์ ๋์ ๋ ์๊ฐ์ ํธ๋ํน ๋ฐ ํน์ ์๊ฐ ์ดํ์ธ์ง ์ ๋ณด๋ฅผ ์ป๊ธฐ ์ํด์ ๋ค์ต์คํธ๋ผ์ BFS๋ฅผ ๋ ์ฌ๋ฆด ์ ์๋ค.
๋ด๊ฐ ์ ๊ทผ ํ ๋ฐฉ๋ฒ์ ๋ค์ต์คํธ๋ผ์ ๊ฐ๋ ์ธ ์์ ํ ์๋ฃ๊ตฌ์กฐ์ธ heapify ๋ก ํจ์จํ๋ฅผ ํ์ง ์๊ณ , ํ๋ฅผ ํตํด ๋จผ์ road ๋ค์์ ๋ฐฉ๋ฌธํ ๋ง์๊ณผ ๋์ ์๊ฐ์ ๊ฐ์ด ์ ์ฅํ๋ค.
์ด ๋ฌธ์ ๋ ๊ณ์๋๋ ์คํจ๋ฅผ ๋ณด๊ฒ ๋์๋๋ฐ ์คํฐ๋ ์ฅ ๋์ ํตํด ๋์ ์์ด๋์ด์ ๊ตฌํ์ ๋ชจ์์ ๊นจ๋ซ๊ฒ ๋์๋ค.
์ค์ํ ์ ์
- ๋ ธ๋์ ๋ฐฉ๋ฌธ ์ฌ๋ถ ๋ฟ๋ง ์๋๋ผ, ๊ทธ ๋ ธ๋์ ๋๋ฌํ๋ ๋ฐ ๋๋ ์ต์ ๋น์ฉ๋ ํจ๊ป ๊ณ ๋ คํด์ผ ํจ.
- ๊ตฌํ : visited ๋ฐฐ์ด์ ๋ฐฉ๋ฌธ ์ฌ๋ถ ๋์ ํด๋น ๋ ธ๋์ ๋๋ฌํ๋ ์ต์ ๋น์ฉ์ผ๋ก ์ฌ์ฉ
function solution(N, road, K) {
// adjacency list
let adj_list = []
for (const [from, to, w] of road) {
if (!adj_list[from]) adj_list[from] = []
adj_list[from].push([to, w])
if (!adj_list[to]) adj_list[to] = []
adj_list[to].push([from, w])
}
let MAX_K = 500_001
let visited = Array.from({ length: N + 1 }, () => MAX_K)
// bfs
// queue
let START = 1
let queue = [[START, 0]]
let pathSet = new Set()
// while
while (queue.length) {
let [v, w] = queue.shift()
//์ธ๊ทผ ๋ง์
adj_list[v]?.forEach((info, i) => {
// queue์ ๋ฃ์ ๋ [๋ง์, ํ์ฌ ๊ฐ์ค์น + ํฉ์ฐ ๊ฐ์ค์น ]
const [adj_v, adj_w] = info
let future_w = w + adj_w
if (future_w <= K && future_w < visited[adj_v]) {
queue.push([adj_v, future_w])
visited[adj_v] = future_w
}
})
}
return visited.filter((v) => v !== MAX_K).length
}
์ ๋ ฅ๋ง์ ๋๋ก ๋๋๊ธฐ
๋ฌธ์ ๋ฐ๋ก ๋ณด๋ฌ ๊ฐ๊ธฐ (๋ฌธ์ ์ถ์ฒ : ํ๋ก๊ทธ๋๋จธ์ค )
n๊ฐ์ ์ก์ ํ์ด ์ ์ ์ ํตํด ํ๋์ ํธ๋ฆฌ ํํ๋ก ์ฐ๊ฒฐ๋์ด ์์ต๋๋ค. ๋น์ ์ ์ด ์ ์ ๋ค ์ค ํ๋๋ฅผ ๋์ด์ ํ์ฌ์ ์ ๋ ฅ๋ง ๋คํธ์ํฌ๋ฅผ 2๊ฐ๋ก ๋ถํ ํ๋ ค๊ณ ํฉ๋๋ค. ์ด๋, ๋ ์ ๋ ฅ๋ง์ด ๊ฐ๊ฒ ๋๋ ์ก์ ํ์ ๊ฐ์๋ฅผ ์ต๋ํ ๋น์ทํ๊ฒ ๋ง์ถ๊ณ ์ ํฉ๋๋ค. ์ก์ ํ์ ๊ฐ์ n, ๊ทธ๋ฆฌ๊ณ ์ ์ ์ ๋ณด wires๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง๋๋ค. ์ ์ ๋ค ์ค ํ๋๋ฅผ ๋์ด์ ์ก์ ํ ๊ฐ์๊ฐ ๊ฐ๋ฅํ ๋น์ทํ๋๋ก ๋ ์ ๋ ฅ๋ง์ผ๋ก ๋๋์์ ๋, ๋ ์ ๋ ฅ๋ง์ด ๊ฐ์ง๊ณ ์๋ ์ก์ ํ ๊ฐ์์ ์ฐจ์ด(์ ๋๊ฐ)๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
๋ฌธ์ ์์ ์ด๋ ค์ ๋ ๋ถ๋ถ์ ์ ์ ๋ค ์ค ํ๋๋ฅผ ๋์ด์
๋ฅผ ์ด๋ป๊ฒ ๊ตฌํํด์ผ ํ ์ง ๊ฐ์ด ์กํ์ง ์๋๋ค๋ ๊ฒ์ด๋ค.
๋ฌธ์ ๋ฅผ ๋ค์ ํ์
ํ๋ฉด ํํธ๋ฅผ ์ป์ ์ ์๋ค.
๋ฌธ์ ์์ ํํธ๋ก ํธ๋ฆฌ ํํ ๊ฐ ์ฃผ์ด์ก๋ค. ์ด๋ฅผ ํตํด ์ฌ์ดํด์ด ์๋ค๋ ์ ๊ณผ ํ์ฌ ๋
ธ๋ ๋ค์ ์ฐ๊ฒฐ๋์ด ์์์ ์ ์ ์๋ค. ๊ทธ๋ฆฌ๊ณ wires
๋ฅผ ํตํด ์ด๋ ์ ์ ๋
ธ๋๊ฐ ์ด์ด ์ก๋์ง ๋ช
์์ ์ผ๋ก ์๋ ค์ ธ ์๋ค. wires์ ์์ ์ฆ ์ฐ๊ฒฐ๋ ๋
ธ๋ ๋๊ฐ๋ฅผ ์ ์ฒด ๋
ธ๋์์ ์ ๊ฑฐ ํด์ค์ผ๋ก์จ ์ ์ ๋ค ์ค ํ๋๋ฅผ ๋์ด์
๋ฅผ ๊ตฌํํ ์ ์๋ค.
function solution(n, wires) {
let adj_list = Array.from({ length: n + 1 }, () => [])
wires.forEach(([from, to]) => {
adj_list[from].push(to)
adj_list[to].push(from)
})
let mins = []
// wires๋ฅผ ์ํํ๋ฉด์ ๊ฐ์ ๋นผ๊ธฐ
wires.forEach((wire) => {
let visited = new Set()
let deep_copy_adj = adj_list.map((row) => row.slice())
const [a, b] = wire
deep_copy_adj[a].splice(deep_copy_adj[a].indexOf(b), 1)
deep_copy_adj[b].splice(deep_copy_adj[b].indexOf(a), 1)
let subtraction = 0
//์ฐ๊ฒฐ๋์ด์ง ๋
ธ๋ ๊ฐ์ ๊ตฌํ๊ธฐ
for (let i = 1; i <= n; i++) {
if (visited.has(i)) continue // ๋ฐฉ๋ฌธํ ๋
ธ๋๋ฉด continue
let result1 = dfs(i, 0, deep_copy_adj, visited) // ์ฐ๊ฒฐ ๋
ธ๋ ๊ฐ์
subtraction = result1 - subtraction //์ฒซ ์งํฉ์ subtraction์ผ๋ก ํ ๋น, ๋๋ฒ ์งธ ์งํฉ์ ๋นผ๊ธฐ
}
mins.push(Math.abs(subtraction))
})
return Math.min(...mins)
function dfs(i, level, adj_list, visited) {
visited.add(i)
level += 1
adj_list[i].forEach((v) => {
if (visited.has(v)) return false
level = dfs(v, level, adj_list, visited)
})
return level
}
}
๊ฒฝ์ฃผ๋ก ๊ฑด์ค
ํ ์ผ์์ ์๊ฐ๋ณต์ก๋๋ ์์ ํ๊ฒ ๊ฐ์ ธ๊ฐ๊ธฐ ์ํด ํ์ด์ฌ์ผ๋ก ๋น ๋ฅด๊ฒ heapq๋ฅผ ์ ์ฉํด๋ณด์๋ค.
์ ์ถ ์ ์คํจ ํ ์คํธ ์ผ์ด์ค 24 ใ ์คํจ (0.11ms, 10.4MB) 92% ์ด์ ์ ๋ฐฉ๋ฌธํ ๋ฐฉํฅ์ ์ฒ๋ฆฌํ๋ ๋ถ๋ถ์ ๋ค์ ๋ด์ผ ํ ๊ฒ ๊ฐ๋ค.
def solution(board):
dy=[-1,0,1,0] #๋ถ๋๋จ์
dx=[0,1,0,-1]
hq= []
heapq.heappush(hq, (0,None,0,0))
visited = [ [float("inf")]*len(board) for i in range(len(board)) ]
while(hq):
w, axis, y, x =heapq.heappop(hq)
_axis = axis
print(w, axis, y, x)
for i in range(4):
nx= x+dx[i]
ny = y+dy[i]
if(nx<0 or ny<0 or nx>=len(board) or ny>=len(board) or board[ny][nx] ==1):
continue
if axis == None:
if( ny == y and nx!=x):
_axis = "x"
elif(nx == x and ny!=y):
_axis = "y"
next_axis = _axis
if( ny == y and nx!=x):
next_axis = "x"
elif(nx == x and ny!=y):
next_axis = "y"
isCorner = _axis != next_axis
corner_w = 500 if isCorner else 0
next_w = w+100+corner_w
# visited ๊ฐ๊ณผ ๋น๊ต ํ์ฌ ์์ผ๋ฉด visited ๊ฐ ๊ฐฑ์
if next_w <= visited[ny][nx]:
visited[ny][nx] = next_w
heapq.heappush(hq, (next_w, next_axis, ny, nx)) #heapq์ ๋ฃ๊ธฐ
print(visited[-1][-1])
return visited[-1][-1]