[백준 31809] malware 박멸하기 : https://www.acmicpc.net/problem/31809문제 조건시간을 신경쓸 필요가 없어보인다. 하루에 박멸 이후 감염이 차례로 진행된다고 이해할 수 있다. 따라서 자신에게 진입 간선이 존재한다면 박멸 이후 감염이 이뤄지므로 아무런 일도 일어나지 않는다. 위에서 말했던 것에 대한 예시를 확인할 수 있다. 진입 간선이 존재한다면, 박멸 이후 감염된다.주기(P)와 C의 크기가 다른 것이 처음 문제를 읽을 때 조금 헷갈렸다.  문제 해결 방법 문제의 핵심은 현재 박멸이 진행되는 컴퓨터(노드)에 진입하는 간선(즉, 외부에서 감염될 가능성)이 있다면, 해당 컴퓨터는 다시 감염될 수 있어 즉시 처리할 수 없다는 점이다.따라서 진입 간선이 없는 노드를 우선적..

[백준 4196] 도미노 : https://www.acmicpc.net/problem/4196문제 조건 도미노가 한쪽 방향으로만 넘어지기에 단방향 간선으로 표현되지만, 실제로는 우리가 원하는 방향(왼쪽 또는 오른쪽)으로 도미노를 밀어 넘어뜨릴 수 있다. 즉, 한 도미노가 넘어진 방향에 따라 연쇄 반응을 일으키는 관계가 결정되는데, 이때 도미노를 그래프로 나타내면 간선이 기본적으로 한 방향(진출 간선)만 표시된다. 하지만 만약 어떤 도미노가 한쪽 방향에서는 연쇄 반응을 일으키지 못한다면, 그 도미노의 반대쪽(진입 간선) 방향으로도 연쇄 반응을 고려할 수 있어야 한다. 그래서 DFS를 진행할 때, 상황에 따라 진출 간선과 진입 간선을 서로 뒤바꿔서 탐색할 수 있다는 뜻이다. 이는 단순히 양방향 그래프가 되는..

https://school.programmers.co.kr/learn/courses/30/lessons/49191 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 접근 방법 위상 정렬위상 정렬로 열내면서 풀어봤지만 문제를 풀수록 미궁 속으로 빠졌다. 위상 정렬로 풀이하면 처음과 끝에 있는 선수들의 순위는 비교적 쉽게 정할 수  있지만, 중간에 있는 선수들의 순위는 모호하고, 접근하기 까다로워진다. 문제를 풀면서 이상하다고 생각해서 찾아보니 위상 정렬은 순서가 명확히 정해진 상황에서 사용하는 게 올바르다고 한다.(순서가 명확, 사이클X -> 위상 정렬) 플..

[백준 22954] 그래프 트리 분할 : https://www.acmicpc.net/problem/22954문제 조건 정리 정점 𝑁개, 간선 𝑀개의 그래프가 주어진다.각 정점은 1부터 𝑁까지 번호가 매겨져 있고,간선도 입력되는 순서대로 1부터 𝑀까지 번호가 매겨져 있다.그래프에서 원하는 만큼 간선을 삭제해, 서로 다른 크기의 트리 2개로 분할해 보자!각각의 트리는 하나 이상의 정점을 가지고 있어야 하며, 두 트리가 동일한 정점이나 간선을 공유해서는 안 된다.입력과 출력   문제를 풀기 전 그래프를 분할할 수 없는 경우를 올바르게 짚는다면 효율적으로 해결할 수 있다.2개의 트리로 분할할 수 없는 경우    -> 주어지는 정점 개수가 1개    -> 진작에 3개 이상의 분할된 그래프가 주어짐 (간선으..

[백준 14466] 소가 길을 건너간 이유 6 : https://www.acmicpc.net/problem/14466문제 조건 정리 정사각형 목초지가 N×N (2 ≤ N ≤ 100) 격자로 이루어져 있다.인접한 목초지 사이는 일반적으로 자유롭게 건너갈 수 있지만, 그 중 일부는 길을 건너야 한다. -> 사실상 (길 == 벽)농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다. -> 테두리 검사해야함K마리의 (1 ≤ K ≤ 100,K ≤ N2) 소가 존의 농장에 있고, 각 소는 서로 다른 목초지에 있다.어떤 두 소는 길을 건너지 않으면 만나지 못 할 수 있다. 이런 소가 몇 쌍인지 세어보자. -> 쌍 공식 -> K*(K-1)/2입력 첫 줄에 N, K, R이 주어진다.다음 R줄에는 한 줄..