이숭간 공부기록

https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 문제유형: BFS,그래프탐색, 문제풀이 : 비활성 바이러스에 활성바이러스가 닿으면 비활성도 활성이 된다..... 는 것을 문제에서 놓침. 또 이때에는 시간이 증가하지 않음 그냥 변하기만함.. 활성바이러스가 빈칸으로 복제될때만 시간이 증가하는것이고 바이러스에 닿으면 그냥 변하게만 한다. 가능한 m개의 바이러스 조합에 대해 bfs를 돌려야되는데 이때 graph를 deepcopy하면 시간초과가난다. graph는..

https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 문제유형 : BFS 문제풀이 : BFS로 인접한 국가들을 방문하며 푸는 문제 문제에서 '다른국가를 거쳐가도(심지어 이미 방문한국가라도)된다. 라는 말이 나오는데 bfs로풀때 만약 2의 인접한 국가가 3,4라고 했을때 2->3, 2->4 으로 뻗어나가기때문에 2번이 2번 방문되어도 된다 이런의미로 해석하면 된다. 큐에 국가를 넣을때마다 비행기를 한번 탔다는것을 ..

https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 문제유형 : DFS/BFS 문제풀이 DFS의 경로상에 순서가 있는경우 (a-b-c 와 a-c-b가 다른경우!!) dfs의 재귀호출이 리턴되는 지점에서 방문처리를 다시 풀어줘야한다 단어가 하나의 노드가되고 차이가 1인 노드끼리 연결되있다고 생각한다. 현재노드로부터 차이가 1인 노드들을 순차적으로 방문탐색하면서 target..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제유형 : 구현, 그래프탐색 (삼성기출) 문제풀이 BFS(DFS도 가능)를 통해 연합가능한 국가를 찾도록 한다. 전체국가를 돌면서 bfs로 연합가능한 국가의덩어리들을 찾고 각 덩어리들사이에서 인구이동을 진행한다. 모든칸(전체국가)을 돌았는데 인구이동이 한번도 없었다면 더이상 진행이 불가한것을 의미하므로 while문을 break하고 빠져나온다. 인구이동이 있었다면, 다시 visite..