본문 바로가기
👩‍💻 Programming/Coding Test 문제 풀이

[이코테] DFS/BFS_음료수 얼려 먹기(자바스크립트)

by codingBear 2023. 1. 16.
728x90
반응형

이번 글은 '이것이 취업을 위한 코딩테스트다' 내의 문제를 풀고 정답 코드를 정리한 것입니다.

 

이것이 취업을 위한 코딩 테스트다 with 파이썬 | 나동빈 - 교보문고

이것이 취업을 위한 코딩 테스트다 with 파이썬 | IT 취준생이라면 누구나 입사하고 싶은 카카오ㆍ삼성전자ㆍ네이버ㆍ라인! 취업의 성공 열쇠는 알고리즘 인터뷰에 있다!IT 취준생이라면 누구나

product.kyobobook.co.kr


👨‍💻 문제


정답 코드

답안 1

답안 2


문제 풀이

 이 문제는 dfs를 활용해서 풀 수 있다. 우선 이중 for 문을 활용해 2차원 배열의 모든 요소를 시작 지점 (0, 0)에서부터 탐색해나간다. 이때 현재 탐색하는 노드의 값이 0이라면 dfs 함수로 진입해서 상하좌우의 모든 요소를 탐색한다. 상하좌우의 노드 중 방문 가능한 노드가 있다면 방문 처리를 하고 다시 dfs를 재귀적으로 반복한다. dfs를 반복해서 호출하다가 방문 가능한 인접 노드가 없을 경우 원래 탐색 중이던 노드에서 위치를 옮기고, 위의 과정을 반복한다.

 즉 (0, 0)부터 시작한다면 (0, 0)과 인접한 노드들 중 방문 가능한 노드가 없을 때까지 모든 노드의 값을 1로 바꾸고 다음 탐색할 노드를 찾는 과정을 반복하는 것이다.


함께 보기

 

[DFS] 이코테 “음료수 얼려 먹기” Python 풀이

문제 N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로

wooono.tistory.com

 

 

[DFS/BFS] (이코테) 음료수 얼려 먹기 - 파이썬(Python)

매일매일 알고리즘 공부하기

yganalyst.github.io

 

728x90
반응형

댓글