본문 바로가기

알고리즘/백준

 (263)
[백준] 5427번 : 불 5427번: 불 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 🤔 문제분석 너비우선탐색을 이해하면 쉽게 풀 수 있는데, 불을 먼저 방문한뒤 승범이를 방문하면 불이 먼저 번지게되고 번지지 않은 위치를 승범이가 탐색 할 수 있으니 문제에서 요구하는 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동 할 수 없는 조건을 잘 만족 시킬 수 있습니다. 💻 코드 import sys from collections import deque input = sys.stdin.readline moves = [(0, 1), (0, -1), ..
[백준] 1774번 : 우주신과의 교감 1774번: 우주신과의 교감 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 🤔 문제분석 우주신끼르는 가장 짧은 길이로 연결되어야한다. 최소신장 트리를 이용하여 문제를 해결하면된다. 최소 신장 트리는 가장 짧은 간선을 사이클이 존재하지 않을때까지 반복하여 유니온한다. 💻 코드 import sys input = sys.stdin.readline N, M = map(int, input().split()) node = [] for _ in range(N): X, Y = map(int, i..
[백준] 1956 : 운동 1956번: 운동 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 🤔 문제분석 사이클이 존재하면서 두 마을 사이의 거리중에서 가장 짧은 거리를 구하는 문제로 플로이드 워셜을 이용하여 문제를 해결한다. 플로이드 워셜은 i번째 마을에서 j번째 마을까지 최단경로를 구한다. 모든 i와 j에 대해서 (i번째 마을에서 j번째 마을까지 + j번째 마을에서 i번째 마을까지) 를 구하게 되면 가장 짧은 사이클을 구할 수 있다. 만약 i와 j가 연결되어있지 않다면 INF로 둔다. 💻 코드 im..
[백준] 4386번 : 별자리 만들기 4386번: 별자리 만들기 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 🤔 문제분석 간선의 개수를 작은 것부터 하나씩 그려나아가면서 가장 짧은 간선으로 모든 노드를 연결 할 수 있는 방법은 최소신장트리이다. 최소신장 트리를 구현하기위해서 유니온-파인트 자료구조를 활용하여 문제를 해결한다. 💻 코드 import sys from math import sqrt input = sys.stdin.readline def get_distance(y1, x1, y2, x2): y = pow(abs(int((y1*100 -..
[백준] 1963번 : 소수경로 1963번: 소수 경로 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 🤔 문제분석 모든 숫자를 대입해보면서(완전탐색) 소수이고 방문하지 않는 소수만 방문해(너비우선탐색)나아가면서 문제를 해결하면 된다. 4자리 숫자이기 때문에 시간내에 문제를 해결 할 수 있습니다. 참고 : 소수를 판별하는 방법은 제곱근의 수 + 1 만큼만 비교하면 된다. (에라토스테네스의 체) 💻 코드 import sys input = sys.stdin.readline from collections import deque def is_prime(nu..
[백준] 6593번 : 상범 빌딩 6593번: 상범 빌딩 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 🤔 문제분석 3차원 배열에서 너비우선탐색을 이용하면 된다, 가로,세로,높이를 입력받고 갈수 있는 방향은 6가지로 모든 경우의수를 너비우선탐색으로 방문해가면서 도달 할 수 있는지 체크하면 된다. 💻 코드 import sys from collections import deque input = sys.stdin.readline moves = [(0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 0, -1), (0, -1, 0), (-1..
[백준] 2458번 : 키 순서 2458번: 키 순서 🤔 문제분석 플로이드 워셜로 문제를 접근하면 됩니다. s에서 g로 갈 수 있는 경로가 존재한다는것을 모두 파악한 뒤에 해당 그래프가 다른 그래프와 모두 연결되어있는지 확인하면 됩니다. 💻 코드 import sys input = sys.stdin.readline N, M = map(int,input().split()) arr = [[0] * (N+1) for _ in range(N+1)] for _ in range(M): small, big = map(int,input().split()) arr[big][small] = 1 for k in range(1,N+1): for s in range(1,N+1): if k==s: continue for g in range(1,N+1): if g..
[백준] 1865번 : 웜홀 1865번: 웜홀 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 🤔 문제분석 밸만포드로 문제를 해결할 수 있습니다. 어떠한 노드에서 출발해도 상관이 없기때문에 1번 노드에서 출발 하여 문제를 해결하였습니다. 💻 코드 import sys input = sys.stdin.readline TC = int(input()) def bellman_ford(start): distance = [INF for _ in range(N+1)] distance[start] = 0 for n in range(N): f..

티스토리툴바