문제https://www.acmicpc.net/problem/1707풀이 이분 그래프를 판별하는 문제이다. 이분 그래프는 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프를 말한다. 풀이는 간단한데, 방문 시 1과 -1의 값으로 번갈아가며 방문 배열을 채워나가고, 만약 이전 방문 배열 값과 다음 방문 배열 값이 같으면 NO를 출력하면 끝이다. 그런데 여기서 주의해야할 것은 이분 그래프의 정의인데, 연결되지 않은 정점도 독립적인 그룹으로 이분 그래프의 조건을 만족한다. 그래서 탐색을 시작할 시작점은 방문되지 않은 점이 대상이 된다. (즉 모든 정점이 연결되어 있다고는 가정되어있지 않다! 이것땜에 43프로에서 틀렸다.) 다음은 소스 코드이다.소스 코드import..
BFS
문제https://www.acmicpc.net/problem/11559 풀이bfs가 포함된 빡 구현 문제이다. 제거할 뿌요를 bfs로 찾고, 삭제하고, 중력을 통해 재 정렬을 해야한다. 여러 그룹의 삭제될 뿌요가 한 텀에 있어도 연쇄는 한 번이라는 것을 잊으면 안된다. 여기서 연속된 4개 이상이 연결된 뿌요를 찾아 제거해야하는데, 그냥 BFS를 사용해 탐색하면, ㅓ ㅏ ㅗ ㅜ 모양의 탐색은 visited에 걸려 탐색을 할 수가 없다. 이것은 단순하게 해결 가능한데, 최대 2번까지 방문을 허용하기만 하면 ㅓ ㅏ ㅗ ㅜ 탐색이 가능하게 된다. 중력에 의한 재정렬은 stack을 이용해 구현했다. 제거할 뿌요를 제외한 값을 stack에 push하고, 다시 map[][]의 아래부터 stack에서 pop을 하며 값..
문제https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이전형적인 BFS 문제이지만, 자바스크립트로 풀려니 구현 방식에서 고민이 많이 되었다. 우선 처음 작성한 코드를 살펴보며 자바와 다르게 고민했던 부분들을 정리해보겠다.function solution(maps) { var answer = -1; const N = maps.length; const M = maps[0].length; const dr = [-1,1,0,0]; c..
