코딩공부/코딩테스트 (5) 썸네일형 리스트형 BFS / DFS 문제 모음 & 문제 유형 정리 BFS / DFS 의 개념 자체를 모르는 사람은 좋은 블로그 정리글이나 유튜브 영상에서 꼭 배워오세요!!!해당 글은 BFS / DFS의 문제 유형과 문제 접근법들을 정리한 글 입니다!!문제 모음[기초 문제]1. DFS 와 BFS (백준) : https://www.acmicpc.net/problem/12602. Number of islands ( leetcode ) : https://leetcode.com/problems/number-of-islands/3. keys and rooms ( leetcode ) : https://leetcode.com/problems/keys-and-rooms/description/4. shortest path in binary matrix ( leetcode ) : htt.. 백 트래킹 이란? 이번에야 말로 백 트래킹 끝내자(유형 정리, 분석) 백 트래킹 이란? 자신의 선택에 따라서 게임의 엔딩이 여러개 있는 "멀티 엔딩" 장르의 게임이 있다. 가장 큰 예시로 미연시 게임 대부분이 선택에 의해서 게임이 진행 된다. 이때 선택에 따라 다음 선택지가 달라지며 마지막 엔딩까지 선택에 따라 달라지는 것이다. 이런 경우 가장 좋은 엔딩을 어떻게 찾을까? 이때 사용되는 알고리즘이 "백 트래킹"이다. 일단 선택을 쭉 하고 좋지않거나 성립되지 않는 경우 다시 백 해서 다른 선택을 하여 모든 경우의 엔딩을 찾는 것이다. "선택의 DFS" 라고도 할 수 있다. 어떻게 구현 하는가? "선택의 DFS" 라고 표현 했듯이 백 트래킹은 재귀함수를 이용해서 구현 한다. 기본적인 구현 틀은 아래와 같다. 이때 parameter를 어떻게 하는지, 어느 조건에서 재귀를 멈추는.. [백준 2580] 스도쿠 (파이썬) 문제 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이 # 83% 시간초과 # pypy 통과 import sys input = sys.stdin.readline from collections import deque graph = [list(map(int, input().split())) for _ in range(9)] blanks = deque() for row in range(9): for col in range(9): if graph[.. 합승 택시 요금 _ 카카오 코딩 테스트 (파이썬, 최단거리, 프로그래머스) 문제 https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 import sys input = sys.stdin.readline INF = int(1e9) def solution(n, s, a, b, fares): graph = [[INF]*(n) for _ in range(n)] for n1, n2, w in fares: graph[n1-1][n2-1] = w graph[n2-1][n1-1] = w for i in range(n): for j .. [백준 1753번] 최단경로 (feat. 파이썬) 문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이 import sys input = sys.stdin.readline from heapq import heappop, heappush INF = int(1e9) V, E = map(int, input().split()) start = int(input()) graph = [[] for _ in range(V+1)] for _ in range(E): n.. 이전 1 다음
