본문 바로가기

알고리즘/백준

 (263)
[백준] 1613번 : 역사 1613번: 역사 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 🤔 문제분석 위상정렬과 플로이드 워셜로 풀 수 있는 문제입니다. 저는 처음에 문제를 풀때 위상정렬로 접근하였습니다. 위상정렬을 할때에 **부모노드를 자식노드에 업데이트(부모노드는 자식노드에게 내가 너보다 먼저 야 라고 표시)**하면서 자기자신을 방문할때 자기자신을 추가하면 됩니다. 💻 코드 import sys input = sys.stdin.readline INF = sys.maxsize n, k = map(int, input().spl..
[백준] 4179번 : 불! 4179번: 불! 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 🤔 문제분석 불, 지훈 순으로 큐에 넣고 너비우선탐색을 하여 지훈이 그래프의 끝자락에 도착 할 수 있는 거리 + 1을 계산해주면된다. 만약, 불이 지훈이를 가로막는다면 지훈이는 갈 수 없다. 💻 코드 import sys input = sys.stdin.readline from collections import deque R, C = map(int, input().split()) table = [] queue = deque() j..
[백준] 11779번 : 최소비용 구하기2 11779번: 최소비용 구하기 2 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 🤔 문제분석 우선순위큐를 이용하여 문제를 해결하였는데요, 예전에 풀었던 유형이랑 비슷해서 문제를 쉽게 풀 수 있었습니다. 방문 경로를 구하는 로직은 거꾸로 우선순위큐를 역추적 하면됩니다. 말로는 어렵지만 코드를 보면 쉽게 이해 할 수 있습니다. 💻 코드 import sys import heapq input = sys.stdin.readline INF = sys.maxsize n = int(input..
[백준] 12851번 : 숨바꼭질 2 12851번: 숨바꼭질 2 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 🤔 문제분석 너비우선탐색으로 문제를 해결하였는데 처음 방문한경우와 이전위치에서 오는 경우 두가지를 따져서 모든 경우의 수를 구해야합니다. 💻 코드 import sys from collections import deque input = sys.stdin.readline N, K = map(int, input().split()) vistied = [-1] * 100001 queue = deque() qu..
[백준] 1600번 : 말이 되고픈 원숭이 1600번: 말이 되고픈 원숭이 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 🤔 문제분석 너비우선탐색과 방문배열을 K차원으로 두어 문제를 해결하였습니다. 너비우선탐색을 하게되면 x,y좌표에서 i번 움직였을때가 가장 최소거리임으로 3차원 배열을 만듭니다. 시작점으로부터 원숭이가 이동하는 방법과 말과 이동하는 방법 모두 탐색합니다. 💻 코드 import sys from collections import deque input = sys.stdin.readline K = int(input()) W..
[백준] 20056번 : 마법사 상어와 파이어볼 20056번: 마법사 상어와 파이어볼 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 🤔 문제분석 문제의 포인트는 1번행과 N번행이 연결되어있고, N번열과 1번열이 연결되어있는 상태를 어떻게 구현할 것인가가 이 문제의 포인트 입니다. chage_dir 함수를 만들었고 해당 함수는 음수가 되든 범위가 넘어가든 상황을 나머지 연산을 활용하여 처리하였습니다. 파이어볼이 여러개 모여있는곳을 딕셔너리를 활용하여 딕셔너리에 리스트를 받고 리스트가 2보다 클경우 파이어볼을 분산시킵니다..
[백준] 1022번 : 소용돌이 예쁘게 출력하기 1022번: 소용돌이 예쁘게 출력하기 1022번: 소용돌이 예쁘게 출력하기 첫째 줄에 네 정수 r1, c1, r2, c2가 주어진다. www.acmicpc.net 🤔 문제분석 회전하는 로직을 구현하는것이 이문제의 핵심이다. 회전은 아래의 사진과 같이 이루어진다. i가 (2, 3, 4, 5 … ) 1씩 증가하면서 두번씩 (좌 or 우), (상 or 하) 움직인다. 그것을 방향은 방향을 다움직이고나서 다음 방향으로 전환 시켜주면 된다. 회전 구현이 다 끝났다면 이제 문제에 조건이 맞는 길이를 맞추어주면 끝 💻 코드 import sys input = sys.stdin.readline r1, c1, r2, c2 = map(int, input().split()) R = r2 - r1 + 1 C = c2 - c1 ..
[백준] 2931번 : 가스관 2931번: 가스관 2931번: 가스관 www.acmicpc.net 🤔 문제분석 너비우선탐색으로 파이프 다음에 빈칸이 나올경우를 구한뒤 그 빈칸이 어떤 파이프가 들어가야하고, 그 파이프가 들어갔을때 기존에 있던 파이프와 호환되는지 확인해서 찾으면 된다. 파이브가 호환되는지 판단하는 로직은 네 방향을 모두 방문 해보면서 그 해당하는 파이프가 그 방향으로 열려있는 파이프를 찾고, 그 방향으로 가르키는 파이프를 추론합니다. 추론하는 방식은 딕셔너리와 배열의 인덱스를 활용하여 찾아내었습니다. 💻 코드 import sys input = sys.stdin.readline from collections import deque pipe_type = ['|','-','+','1','2','3','4'] moves = [..

티스토리툴바