페블_
반짝이는 시냅스
페블_
전체 방문자
오늘
어제
  • 전체글 보기 (96)
    • QA (0)
    • 프로젝트 회고 (4)
    • 프로젝트 과정 기록 (12)
    • UI 구현 연구일지 (8)
    • Front-end (31)
      • Javascript (7)
      • CSS (10)
      • React (5)
      • Typescript (3)
      • Nextjs (3)
      • 스타일링 라이브러리 (3)
    • Back-end (0)
      • Express (0)
      • DB (0)
    • CS (0)
      • 자료구조 & 알고리즘 (0)
    • CI&CD (1)
    • 툴 사용법 (4)
      • Git (1)
      • Library&패키지 (2)
      • 기타 개발관련 (1)
    • 알고리즘 이론 & 풀이 (36)
      • 백준(BOJ) (14)
      • 프로그래머스 (22)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 토이프로젝트
  • 캐러셀
  • UI 컴포넌트
  • Python
  • react
  • 백준
  • TypeScript
  • 개발블로그_시작
  • eslint
  • emotion
  • 시리즈_표지
  • 파이썬
  • chartjs
  • 알고리즘
  • storybook
  • 선형대수학
  • JS
  • 생각

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
페블_

반짝이는 시냅스

알고리즘 이론 & 풀이/백준(BOJ)

[백준] 2178번 - 미로 탐색

2023. 8. 17. 19:27

문제

https://www.acmicpc.net/problem/2178

 

// 입력
4 6
101111
101010
101011
111011

// 출력
15

 

풀이

BFS로 최단거리 찾기 문제.

맨 처음에 풀 때는 백트래킹을 안해줘서 시간제한에 걸렸는데, visitied로 방문했던 곳을 관리해 한번 갔던 곳은 다시 안 가게 했더니 통과했다.

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const [N, M] = input[0].trim().split(' ').map(Number);
const maps = [];

for (let i = 1; i < input.length; i++) {
  maps.push(input[i].trim().split('').map(Number));
}

function solution(N, M, maps) {
  const dx = [1, -1, 0, 0];
  const dy = [0, 0, 1, -1];
  const visitied = Array.from({ length: N }, () => Array(M).fill(false));

  const queue = [];
  queue.push([0, 0, 1]);
  visitied[0][0] = true;

  while (queue.length > 0) {
    const [x, y, count] = queue.shift();
    if (x === M - 1 && y === N - 1) return count;

    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];

      if (
        nx >= 0 &&
        nx < M &&
        ny >= 0 &&
        ny < N &&
        !visitied[ny][nx] &&
        maps[ny][nx] === 1
      ) {
        queue.push([nx, ny, count + 1]);
        visitied[ny][nx] = true;
      }
    }
  }
}
console.log(solution(N, M, maps));

 

'알고리즘 이론 & 풀이 > 백준(BOJ)' 카테고리의 다른 글

[백준] 7576번 토마토 (nodejs)  (1) 2023.11.02
[백준] 1026번 - 보물 (nodejs)  (1) 2023.10.28
[백준] 1260번 - DFS와 BFS (js)  (0) 2023.08.17
[백준] 1158번: 요세푸스 문제 (Python)  (0) 2021.11.01
[백준] 5598번: 카이사르 암호 (Python)  (0) 2021.10.25
    '알고리즘 이론 & 풀이/백준(BOJ)' 카테고리의 다른 글
    • [백준] 7576번 토마토 (nodejs)
    • [백준] 1026번 - 보물 (nodejs)
    • [백준] 1260번 - DFS와 BFS (js)
    • [백준] 1158번: 요세푸스 문제 (Python)
    페블_
    페블_

    티스토리툴바