Dalin's Archive

문제 보러 가기! TMI 내 기억 상 처음으로 푸는 영어 문제이다. 풀이 🦄 문제 이해를 돕기 위한 설명용 그림..ㅎㅎ 처음에 1번 섬에서 무조건 시작하고, 그 병력을 가지고 시작한다. 지배한 섬과 이어진 섬은 공격 후보가 된다. 이어진 섬의 병력이 우리(spanning nation) 병력보다 적을 때만!! 그 섬을 지배한다. 우선순위 큐를 활용하면 된다. 우선순위 큐, q에 공격할 수 있는 후보들(섬)을 집어 넣었다. 인접 리스트로 섬들의 연결 관계를 저장한다. 각 섬의 병력을 island_army 리스트에 저장한다. 각 섬을 공격할 수 있는 후보(q)에 넣었는지 여부를 저장하는 visited 리스트를 만든다. 1번 섬에서 시작한다. 우리 병력(spanning_army_cnt)를 1번 섬의 병력으로 업..

문제로 가기! 처음에는 윗칸의 수를 고르고 그 아래 칸의 수를 보고, 각자 set에 넣어서 두 set이 같은지 다른지 판단해주고.. 같으면 또 다른 (윗칸) 수를 골라보고... 다르면 그 아래칸의 수를 윗칸 수로 하는 수를 찾고... 그런 식으로 생각을 해서 코드를 짜긴 했는데, 틀렸다. 질문 검색에서 다른 분들이 주신 반례를 보고, 그림을 그려보니까 문제가 좀 더 잘 이해되었다. 방향이 있는 그래프(윗 칸 -> 아랫 칸)로 보고, 인접 리스트로 입력을 받았다. DFS로 탐색을 하면서 사이클이 발생한 것을 다 더하면 되는 문제였다. 나는 set을 활용해서 윗 칸의 수들의 집합, 아랫 칸의 수들의 집합이 일치하는지 보았다. 만약 일치하면 일치하는 집합을(윗 칸 수들의 집합이든 아랫 칸 수들의 집합이든 같으..