KEEP GOING

https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 처음에 엥 이게 왜 dfs 문제지? 하고 while True 문을 이용해 물고기 이동, 제일 덩치 큰(번호가 높은) 물고기를 골라 상어의 식사를 마치고 상어가 벽을 만나면 그대로 종료하는 식으로 풀이하였다. 그러나.. 이 문제는 '상어가 먹을 수 있는 물고기 번호의 최댓값을 구하는 문제'이다. 따라서 벽을 만나지 않으면서 최대한 많은 물고기를 잡아먹도록 구현해야 한다. 그렇기 때..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 1. union find로 구현 # 정점, 간선의 개수 n, m = map(int, input().split()) graph = [[] for _ in range(n+1)] parent = [i for i in range(n+1)] def find(x, parent): if parent[x] != x: return find(parent..

* BFS (Breath-Frist Search) - 너비 우선 탐색 - 큐(deque) 사용 - 현재 위치에서 가장 가까운 노드들을 모두 방문 - 현재 위치 pop, 방문할 곳 append, 방문한 곳 check ☞ 미로 탐색 중 최단 거리를 찾는 문제 ☞ 임의의 경로를 찾는 문제 BFS 장/단점 - 장점: 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장함 - 단점: 경로가 매우 길 경우 탐색가지가 급격히 증가하여 많은 기억 공간이 필요함 해가 존재하지 않는다면 유한 그래프인 경우, 그래프 탐색 후 실패로 끝남 다만 무한 그래프인 경우에는 해를 찾지도 끝내지도 못한다. ex) 우리나라에서 직통도로로 연결된 지역 중, 서울과 경기도 사이에 존재하는 경로를 찾고싶을 때 깊이 우선 탐색의 경우(DF..

1. dfs 사용 # B 이상인 height 중에서 가장 작은 height 구하기 def backtracking(N, B, height, idx): global result # 마지막 원소까지 더해버렸다면 if idx >= N: # 선반의 높이 이상이고 최소값보다 작을때 갱신 if B

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 코드 구현 (bfs 풀이) from collections import deque move = [(1,0),(0,1),(-1,0),(0,-1)] def bfs(x, y): deq = deque([(x,y)]) while deq: x, y = deq.popleft() for dx, dy in move: nx = dx + x ny = dy + y if 0

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 코드 구현 (방문처리시 dict 사용) from collections import deque def bfs(): que = deque([(N, 0)]) dic = dict() while que: now, count = que.popleft() # 해당 숫자를 이미 방문한 경우 if dic.get(now, 0): continue # 방문하지 않는 숫자인 경우 dic[now] = 1 if now == M: return count count..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net from collections import deque import sys sys.stdin = open('in3.txt', 'r') n, l, r = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(n)] dx = [1,0,-1,0] dy = [0,1,0,-1] def process(x..

https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 1. 시간초과 발생한 코드 import sys input = sys.stdin.readline n, k = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(n)] time, x, y = map(int, input().split()) dx = [1, 0, -1, 0] dy..