본문 바로가기

Algorithm/Graph188

[파이썬] 백준 11280 : 2-SAT - 3 (플레4) [파이썬] 백준 11280 : 2-SAT - 3 (플레4)https://www.acmicpc.net/problem/11280풀이방향성 생각2 SAT 기본 문제입력이 들어오면 음수 노드를 양수로 만들어서 매핑해준다.풀고 알았는데, 보통 짝수를 참, 홀수를 거짓으로 매핑해서 각 node 0을 새로운 new node 0,1로 매핑한다.명제가 들어오면 전처리 이후, 대우 명제와 함께 그래프에 넣어주기.한 SCC 내에 x와 ~x가 같이 존재하면 모순이므로 명제를 참으로 만들 수 없다. 전체코드import syssys.setrecursionlimit(10**6)input = lambda : sys.stdin.readline().strip()# 입력N,M = map(int,input().split())cvt = la.. 2025. 4. 16.
[파이썬] 백준 17472 : 다리 만들기 2 (골드1) [파이썬] 백준 17472 : 다리 만들기 2 (골드1)https://www.acmicpc.net/problem/17472풀이방향성 생각맵이 작고 섬의 수가 적어서 완탐가능MST로 풀이 시, 크루스칼로 그리디 하게 고르면 전부 탐색하지 않고 풀이 가능. 전체코드from collections import dequedires = [(1,0),(0,1),(-1,0),(0,-1)]inside = lambda x,y : 0 3: G.append([len(locs)-2,table[locs[0]],table[locs[-1]]])G.sort()P = [i for i in range(number)]def find(x): if x != P[x]: P[x] = find(P[x]).. 2025. 4. 12.
[자바] SWEA 7793 : 오! 나의 여신님 (D5) [자바] SWEA 7793 : 오! 나의 여신님 (D5) SWEA 7793 : 오! 나의 여신님풀이방향성 생각멀티소스 BFS악마의 우선순위가 캐릭터의 우선순위보다 높게 설정해서 문제 풀이한다.큐에 먼저 담아주면 된다.악마는 여러개인 것에 주의하기 전체코드import java.util.*;import java.io.*;public class Solution { static int H, W; static char[][] arr; static int[][] V; static int[][] dires = {{1,0},{0,1},{-1,0},{0,-1}}; // validation static boolean inside(int x, int y) { return 0 Q.. 2025. 4. 5.
[파이썬] SWEA 1953 : 탈주범검거 (test) [파이썬] SWEA 1953 : 탈주범검거 (test)SWEA 1953 : 탈주범검거풀이방향성 생각각 노드마다 열린 방향을 딕셔너리로 기록하기각 노드마다 이동 시, 둘 다 열려있어야한다.전체코드from collections import dequedires = [(1,0),(0,1),(-1,0),(0,-1)]inside = lambda x,y : 0코멘트. 2025. 4. 5.

티스토리툴바