문제 파악부터 시작 1. 초기에 n+1개의 집합을 이루고 있다. 2. 여기에 합집합 연산과 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산하려한다. 딱봐도 유니온-파인드 알고리즘을 떠올리게끔 만든 문제. 두 원소를 통해 인자가 2개라는 거 파악하고 같은 집합에 포함되어 있는지 확인하려면? find함수를 재귀로 돌려서 노드를 찾고, union 함수로 같으면 반환하고 다르면 합치기

현재 노드들이 같은 그룹에 속해 있는 지~ 같은 그룹으로 합치고 싶을 때! 쓰는 알고리즘이다. #find 1. par 배열은 각 노드의 부모를 담아놓는다. 2. par 배열의 index는 각 노드의 번호이고 그 값은 부모 노드를 의미한다. 처음 모든 노드의 값을 -1이라고 한다. find 함수는 재귀적으로 자신의 부모의 부모를 탐색한다. 부모가 없는 노드를 발견하면 최상위 노드로 볼 수 있다. 최상위 노드를 찾았다면 해당 노드의 값을 리턴한다. 그 이전의 노드들은 최상위 노드의 번호로 자신의 부모 노드를 갱신한다. #union 두 노드를 인자로 받아서 같은 그룹인지 확인하려하는 알고리즘이다. find 함수를 통해서 해당 노드의 부모 노드를 확인한다. 위 함수에서는 인자로 받은 a,b변수에 부모의 노드의 ..

문제부터 파악해보자 1. 크기가 R*C인 목장이 있다. 2. 각각의 칸에는 비어있거나, 양 또는 늑대가 존재 2-1. 양은 이동하지 않고 지키고 있다. 늑대는 인접한 칸을 자유롭게 이동 가능 3. 목장에 울타리를 설치해서 양이 있는 칸으로 늑대가 못가게 막으려고 한다. 입력 1. 첫째줄: 목장 크기 R,C 주어짐 2. 둘째 줄: R개의 줄에 목장의 상태가 주어진다. .은 빈칸, S는 양, W는 늑대 출력 첫째줄: 늑대가 양이 있는 칸으로 갈수 없게 할 수 있다면 1, 갈 수 있다면 0 둘째줄: R개의 줄에 목장의 상태를 출력한다. 울타리는 'D'로 출력한다. 1. 당연히 우선너비탐색이 떠오름 - 전에 게시물이랑 매커니즘은 비슷하다. 2. 첫째줄에 갈 수 있냐 없냐 이분법이다. 둘 중 하나니깐 기본값을 Y..

정의 : 우선 너비 탐색 : 루트 노드나 임의의 노드에서 인접한 노드를 모두 먼저 확인한 후 다음 depth를 탐색 : 큐를 사용해서 데이터 탐색 조건 : 1번 정점을 root 노드로 하여 1번부터 탐색을 시작한다. : 번호가 작은 정점부터 탐색한다. 백준 2178번 미로탐색 문제 N,M 크기의 배열로 표현되는 미로가 있다. 미로에서 1은 이동할 수 있다. 0은 이동할 수 없다. 이때 (1,1)에서 출발해서 N,M의 위치로 이동할 때 지나야 하는 최소의 칸수를 구해라 입력 첫째 줄에 두 정수 n,m이 주어진다. n개의 줄에는 m개의 정수로 미로가 주어진다. 출력 첫째 줄에 지나야하는 최소 칸수 from collections import deque N, M = map(int, input().split())..

문제 해석! 1. 용액 2개를 구분하기 위해 특성값이 있다. 2. 산성은 양의 정수 / 알칼리성은 음수의 정수다. 3. 혼합한 용액의 특성값은 각 용액의 특성값의 합으로 정의 4. 이 때, 특성 값이 0에 가깝게 만들고 싶다. 문제를 딱 보고 든 생각?! 1. 리스트를 이용해야겠구나 2. 리스트를 접근하기 위해 두 값의 위치를 기록할 필요가 있다. -> 아 투포인터 알고리즘을 활용하자 문제의 특수 상황 특정한 값인 0에 가깝도록 하는 값 찾기 아이디어 1. 첫번째 인덱스가 마지막 인덱스보다 작을 때까지 계속 반복 1-1. 만약 차이가 임시값보다 크면 값을 서로 치환 1-2. 합이 0보다 크면 마지막 인덱스를 줄이고, 합이 0보다 작으면 첫번째 인덱스를 늘리자 import java.io.BufferedRe..

이전 포스팅과 비교했을 때, 이건 기본적인 백트래킹의 매커니즘을 이용한다. 첫째 줄에 자연수가 n과 m을 입력받아서 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야한다. import sys #sys.stdin=open("input.txt", "rt") M, N = map(int,input().split()) s = [] def dfs(): if len(s)==N : print(' '.join(map(str,s))) return for i in range(1,M+1): if i not in s: s.append(i) dfs() s.pop() dfs() 이전 포스팅과 ..