본문 바로가기
728x90
반응형

BFS8

[프로그래머스] level 3 블록 이동하기(자바스크립트) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👨‍💻 문제 정답 코드 답안 1 문제 풀이 전형적인 bfs 문제이다. 다만 로봇의 크기가 두 칸이기 때문에 배열을 탐색하면서 두 칸의 좌표를 체크해야 하고, 상하좌우 90도씩 회전이 가능하다는 점에 유의해야 한다. 또한 방문 여부를 체크하기 위해 visited란 배열을 선언하고, 왼쪽 및 오른쪽 좌표를 문자열로 만든 값을 활용한다는 것도 유의점이다. 상하좌우로 회전을 할 수 있는지 여부를 체크할 때 로봇 기준 두 칸의 상하좌우 요소가 0인지 확인하는 작업이 필요하다. bfs 문제를 풀 때 배열 크기를 주어진 .. 2023. 1. 18.
[Baekjoon] 16234 인구 이동(자바스크립트/NodeJs) 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 👨‍💻 문제 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 .. 2023. 1. 18.
[Baekjoon] 18405 경쟁적 전염(자바스크립트/NodeJs) 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 👨‍💻 문제 NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다. 시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른.. 2023. 1. 17.
[Baekjoon] 14052 연구소(자바스크립트/NodeJs) 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 👨‍💻 문제 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 .. 2023. 1. 17.
[Baekjoon] 18352 특정 거리의 도시 찾기(파이썬/자바스크립트/NodeJs) 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 👨‍💻 문제 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다. 예를 들어 N=4, K=2, X=1일 때 다음.. 2023. 1. 17.
[이코테] DFS/BFS_미로 탈출(자바스크립트) 이번 글은 '이것이 취업을 위한 코딩테스트다' 내의 문제를 풀고 정답 코드를 정리한 것입니다. 이것이 취업을 위한 코딩 테스트다 with 파이썬 | 나동빈 - 교보문고 이것이 취업을 위한 코딩 테스트다 with 파이썬 | IT 취준생이라면 누구나 입사하고 싶은 카카오ㆍ삼성전자ㆍ네이버ㆍ라인! 취업의 성공 열쇠는 알고리즘 인터뷰에 있다!IT 취준생이라면 누구나 product.kyobobook.co.kr 👨‍💻 문제 정답 코드 문제 풀이 bfs로 풀 수 있는 문제이다. 왼쪽 끝(0, 0)에서부터 bfs로 2차원 배열 탐색을 시작한다. 탐색 중인 노드의 상하좌우를 확인하여 처음 방문하는 노드가 있을 경우 해당 노드에다 이전 노드의 값을 누적한다. 그런 다음 큐에다 처음 방문한 노드의 좌표를 갱신한다. 이 같은 .. 2023. 1. 16.
DFS/BFS (깊이 우선 탐색/너비 우선 탐색) 이 문제를 다 풀고 나서 다른 사람들이 짜놓은 코드를 보는데 'DFS'라는 개념이 등장했다. 이전부터 어렴풋이는 알고 있었지만 막상 코드를 읽으니 어떻게 돌아가는지 머릿속에 잘 그려지지 않았다. 어차피 공부해야 하는 내용이니 이참에 확실히 짚고 넘어가야겠다 싶어 정리해보았다. 先요약 DFS BFS 동작 원리 스택 큐 구현 방법 재귀 함수 큐 활용 🤔 DFS(Depth First Search, 깊이 우선 탐색) 🗣 그래프에서 깊은 부분부터 탐색하는 알고리즘. 스택 자료구조 활용. 동작 과정 탐색 시작 노드를 스택에 삽입하고 방문 처리 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드 pop 위의 과정 반복.. 2023. 1. 16.
트리(Tree) References 아래 링크의 강의 중 Section 25. Building a Tree의 내용을 추려 이번 글을 작성하였습니다. The Coding Interview Bootcamp: Algorithms + Data Structures on Udemy Node class Node { constructor(data) { this.data = data; this.children = []; } // node의 입력값 data를 배열로 children에 push add(data) { const node = new Node(data); this.children.push(node); } // filter() method로써 특정값을 제외한 배열을 반환 remove(data) { this.children = th.. 2022. 4. 5.
728x90
반응형

티스토리툴바