게으른 일상로그

인구 이동 문제다. 다 풀고나서 알았는데 삼성 기출문제란다. ㅎㅎ 시간내에 풀었다. 사실 전날까지 MST를 너무 열심히 풀어서인지 아주 자연스럽게 Union-Find로 풀었는데 BFS로 푸는 문제였나보다. 풀이가 죄다 BFS... 완탐문제인줄 알았다. 어찌됐던 내가 생각한 알고리즘은 1. 맵 입력을 받는다. 2. 반복문 시작 3. Union-Find용 연합(group)과 연합을 구성하는 국가의 수(groupCnt, 인구수 x)을 각각 연합 인덱스와 1로 초기화한다. > 인덱스는 나같은 경우 그냥 좌표 그대로 쓰려고 (y*N + x) 형태로 인덱스를 정했다. > 3x3 맵의 (1,0)에 위치한 국가의 인덱스는 3이 된다. 4. 수평(우측)과 수직(하측) 국경을 반복문으로 확인하고 각 좌표별로 열린 국가를 ..

오랜만의 글... 어느정도 알고리즘 공부도 적응 된 것 같아서 괜찮은 것 같은 코드는 올려보려고한다. 포스팅은 나중에 제대로 하도록 하고 간단한 설명과 코드만 일단... 이 문제는 아이디어적으로 크게 어려운건 아니고 BFS와 MST를 조합하는 문제다. 개인적인 생각으로 코테에서 적당한 수준으로 문제를 낸다면 이정도 난이도가 아닐까 싶다. 1. 맵 크기와 키 개수, 맵을 문자열로 입력받는다. 2. BFS로 먼저 시작점부터 각 키까지의 거리, 또 각 키간의 거리를 측정해 그래프화한다. > 제일 기본적인 "queue를 이용한 BFS"를 해주면 된다. 단, 키 부분에 도달시 로봇을 복제를 해줘야 한다. > 이 문제는 MST를 활용하면서 스토리를 더한 문제이지 기본적인 문제이기 때문에 무조건 키에 처음 도달시 한..