OSNIM

문제: https://www.acmicpc.net/problem/10026 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 예를 들어, 그림이 아래와 같은 경우에 RRRBB GGBBB BBBRR BBRRR RRRRR 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2,..

문제 : https://www.acmicpc.net/problem/11724 첫번째 풀이 처음에 서로소 방법인 줄 알고 그래프 이론의 서로소 구하는 방법을 이용하여 구현하려고 했습니다. 코드는 다음과 같습니다. import sys #특정 원소가 속한 집합 찾기 def findParent(parent, v): # 루트노드가 아니라면 루트 노드를 찾을 때 까지 재귀적 호출 if parent[v] != v: parent[v] = findParent(parent, parent[v]) return parent[v] #부모 합치기 def unionParent(parent, v1, v2): v1 = findParent(parent, v1) v2 = findParent(parent, v2) if v1 < v2: par..

문제 출처: https://www.acmicpc.net/problem/19238 나의 접근법 그래프에 남은 연료를 넣기 위해 벽을 -1로 변경 손님들의 위치 정보와 도착정보를 따로 저장 BFS() 1. 먼저 현재 위치에 손님이 있는지 확인 2. BFS로 거리 1차이 나는 거리 확인 -> q에 넣기 3. 같은 거리에 또 다른 손님이 있는지, 첫 손님은 찾았는지, 거리가 같은지 -> custList에 추가 4. 현재 g에 넣는 연료 (남은 연료)가 첫 손님을 찾았을 때 남은 연료보다 작은지 -> 작다면 거리가 같은 손님은 다 찾은 것 -> 정렬 후 행이 낮고 열이 낮은 손님부터 목적지 찾기 5. 가까운 손님을 첫손님을 찾은 경우 -> custList에 추가 5-1 만약 그 첫 손님이 마지막 칸에 있는 경우 ..

문제 출처: https://www.acmicpc.net/problem/17142 나의 접근법 먼저 바이러스 중에서 M개를 선택하는 조합의 경우를 모두 구합니다. 그리고 난 뒤 그래프의 모든 곳을 방문해야 하는데 이를 위해 DFS와 BFS중 무엇을 사용할지 고민 했습니다. 구현을 바로 하기 전에 먼저 DFS로 머리 속에서 시뮬레이션을 돌려봤습니다. 1. DFS로 할 경우 첫번째로 선택한 바이러스의 위치가 모든 곳을 탐색하고 이동할 때 마다 시간을 적습니다. 2. 그 다음 바이러스가 탐색할 때 첫번째 바이러스가 저장한 장소 중 자신이 탐색하는 시간보다 큰 경우에만 탐색을 하며 시간을 업데이트 합니다. 위 방식으로 하게 되면 불필요한 계산이 생기고 방문했던 곳을 또 방문하게 된다면 visited 판단에서 에러..