민규의 흔적

2024년 7월 8일문제 링크 : 백준 2606번 - 바이러스문제  신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때,..

2023년 9월 19일 그래프 탐색 (해당 포스팅은 무향 그래프를 인접 리스트 형태로 다루며 설명을 진행합니다.) 그래프 탐색은 연결되어 있는 그래프의 모든 정점을 지나며 탐색하는 것을 의미한다. ( 그래프 순회라고도 말한다. ) 그래프를 탐색하는 방법으로는 깊이 우선 탐색인 DFS, 너비 우선 탐색인 BFS가 사용된다. DFS ( Depth First Search ) DFS는 출발점에서 시작해, 막다른 지점에 도착할 때까지 최대한 깊게 탐색한다. 만약 탐색을 진행하다 막다른 지점에 도착하면 다시 이전 정점으로 돌아가 다른 길이 있는지 확인하고, 있다면 해당 경로를 최대한 깊게 탐색하다 또 다시 막다른 지점에 도착하면 다시 이전 정점로 돌아가는 과정을 밟는다. 이와 같은 과정을 통해 그래프를 탐색하는 방..

2023년 6월 11일 문제 링크 : 1987번 - 알파벳 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다. 입력 첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적..

2023년 5월 13일문제 링크 : 11400번 - 단절선문제 그래프가 주어졌을 때, 단절선을 모두 구해 출력하는 프로그램을 작성하시오.단절선이란 그 간선을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 간선을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 간선을 말한다.입력첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이며, 방향은 양방향이다.그래프는 항상 연결되어 있으며, 같은 간선이 두 번 이상 들어오는..