링크 : https://www.acmicpc.net/problem/5925 맨날 이런 문제 풀 때마다 헤매는데 또 헤맸다 ㅠㅠ 그리 어려운 문제가 아닌데 왜 맨날 이런 류 문제에서 헤매는지 모르겠다. 주어진 맵에서 3개의 상-하-좌-우로 연결된 조각이 주어지고 이 때 이 걸 1개짜리로 합칠건데 그럴려면 칸을 최소한 몇 개를 더 색칠해야하는 지 물어보는 문제이다. 처음에 BFS로 구현하려다가 이게 반례가 많다는걸 좀 헤매다가 깨닫고 구현을 바꿨다. 근데 그것도 잘 안 돼서 또 더 헤매다가 겨우겨우 품. 굳이 탐색을 안 해도 거리 계산 가능한데 대충 생각하고 탐색으로 구현하려고 한게 문제인 것 같다.
문제 링크 : https://www.acmicpc.net/problem/5858 1차원 선상에서 소가 좌우로 움직이는데 이 때 두 번 이상 방문한 칸의 개수가 몇 개인지 구하는 문제이다. 움직인 총 거리 상한이 10억으로 주어져 있기 때문에, 단순히 움직이는 걸 시뮬레이션하면서 따라가면 시간 초과가 난다. 왼쪽, 오른쪽으로 이동 방향이 두 가지라 헷갈릴 수 있지만, 왼쪽으로 움직였든 오른쪽으로 움직였든 상관없이 특정 위치를 몇 번 방문했는지만 중요하기 때문에 모두 오른쪽으로 움직인 구간으로 생각하고 구간에 들어갈 때 +1, 나갈 때 -1로 배열을 기록해서 만들어 두면 쉽게 계산할 수 있다. 이 때 값이 바뀌는 양 끝 구간 개수는 최대 2N개 생기고, 이 위치를 저장하고 관리하기 위해 map등의 자료 구조..