5/10 백준 업다운 랜덤 디펜스

처음으로 해보는 백준 업다운 랜덤 디펜스.

solved에서 tier:g5 s#100.. 태그로 검색하고 랜덤으로 정렬하여 문제를 푸는 것으로 시작.
1시간 안에 문제를 풀면 다음 문제는 티어를 하나 올리고 풀지 못하면 티어를 하나 내려서 문제를 고른다.

문제를 볼 때 시원시원한 풀이가 바로 떠오르지 않았다. 문자열을 앞에서부터 순회하면서 내가 원하는 문자를 찾으면 해당 문자의 인덱스를 기록하고 다음 문자로 넘어가는 방식을 시험삼아 제출해봤는데 AC를 받았다.

나이브하게 그래프를 전처리 하는 것은 시간 초과가 예상되어 홈의 x,y값 pair를 key로 하는 map을 이용하여 BFS를 구현, AC를 받았다.

처음에는 외판원 순회 문제를 생각했으나 N < 11로 브루트 포스로 문제를 해결해도 시간 초과가 나지 않는 것을 발견.
플로이드 워셜로 각 행성간의 최단 거리를 다시 계산해주고 DFS를 통한 브루트 포스로 AC를 받았다.

친구인 집합끼리 팀을 만들고 친구가 없는 사람은 1인 팀으로 하면 팀의 수가 최대가 된다.
1번 조건은 유니온 파인드로 간단하게 해결이 가능하고 2번 또한 m이 그렇게 크지 않기에 원수 관계를 전부 입력받고 나이브하게 원수의 원수끼리 유니온을 해주면 해결이 가능하다.

오늘 푼 문제들 중 가장 난이도가 높았던 문제. 자세한 풀이는 글을 따로 작성했다.
https://yongjun49.github.io/baekjoon/BOJ(백준)-7976번-수열/

첫날이라 운이 좋은 건지 마지막을 제외하면 무난무난한 그래프 문제들이 나와서 전부 맞힐 수 있었다.

참고