✅문제 ✅문제 풀이 시간 복잡도시간제한이 2초 이기 때문에 어림 잡아 코드가 2억 번 안에 프로그램이 끝나야합니다.최단 경로를 구하는 문제이기 때문에 BFS를 사용하기 때문에 약 1000 * 1000 = 1,000,000번 코드가 실행되고벽을 부시냐 안 부시냐를 나눠서 계산하기 때문에 총 약 2,000,000번 실행되기 때문에 BFS 알고리즘을 사용하면 충분히 시간 안에 문제를 처리할 수 있습니다. 공간복잡도192mb가 공간 제한입니다. 1.2억개의 배열을 생성할 때 512mb가 사용되기 때문에 러프하게 잡아 30,000,000개의 배열을 사용할 수 있습니다. 저희는 BFS와 벽을 안부시냐 부시냐를 체크해야되기 때문에 최대 1000 * 1000 * 2 = 2,000,000개의 배열을 사용하므로 공간 제한..

✅문제✅문제 풀이 그래프를 BFS, DFS로 탐색해서 정점을 방문했는지 안했는지 체크하고 모든 정점을 체크한 것을 기준으로 찾아봅니다. 정점을 방문을 안했다면 1을 더해서 마지막 값을 반환하여 문제를 풀었습니다.✅Codepackage graphbfs;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Beak11724 { public static class Pair { private int x; private int y; public Pair(int x, int y) { thi..

✅문제✅문제 풀이 그래프를 만들어서 DFS, BFS로 탐색한 결과를 출력하는 문제입니다.DFS는 탐색되지 않은 정점을 스택에 추가를 계속하다가 만약에 더 이상갈 곳이 없으면 stack에서 정점을 뱉어냄니다. 그리고 stack이 비어있을때 루프를 빠져나옵니다.BFS는 근처에 있는 탐색되지 않은 정점을 queue를 넣고 queue에서 하나씩 정점을 꺼내 루프를 돌리고 queue가 비어있을때 루프를 빠져나오는 식으로 구현했습니다.✅Codepackage graphbfs;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Beak1260 { ..

✅문제 ✅문제 풀이 가능한 도형을 전부 하나씩 해본다. 배열 한칸 당 총 19개의 경우의 수를 체크해서 끝까지 계산한다. ✅Code Possibleblocks = ( ((0,1), (0,2), (0,3)), ((1,0), (2,0), (3,0)), ((1,0), (1,1), (1,2)), ((0,1), (1,0), (2,0)), ((0,1), (0,2), (1,2)), ((1,0), (2,0), (2,-1)), ((0,1), (0,2), (-1,2)), ((1,0), (2,0), (2,1)), ((0,1), (0,2), (1,0)), ((0,1), (1,1), (2,1)), ((0,1), (1,0), (1,1)), ((0,1), (-1,1), (-1,2)), ((1,0), (1,1), (2,1)), ((..

✅문제 ✅문제 풀이 1. A[i-1] = i 이면서 A[j] > A[i-1]을 만족하는 가장 큰 j 찾기 3. A[i-1], A[j] 스왑 4. A[i] 부터 순열을 뒤집기 ex) 7236541 1. 가장 큰 i 는 6 → A[i-1] = 3 2. A[i-1]이 3 이기 때문에 3보다 크면서 가장 큰 j 찾기 → A[j] = 4 3. A[i-1], A[j] 스왑 → 7246531 4. A[i] 부터 순열 뒤집기 → 7241356 ✅Code def next_permutation(a): i = len(a)-1 while i > 0 and a[i]

✅문제 ✅문제 풀이 BFS를 큐 27개로 수행 - 큐 1개 : 일반적인 BFS - 큐 26개 : 알파벳 문을 위한 큐 1. 테두리에 "." 추가후 BFS 실행 2. 대문자 알파벳 문에 도착했을 때 키가 있으면 그대로 진행 3. 없으면 알파벳 문을 위한 큐에 따로 저장 4. 소문자 알파벳에 도착했을 때는 열쇠가 이미 있을 경우는 그대로 진행 5. 없던 경우는 키를 Set에 추가하고 대문자 알파벳 큐에 넣었던 큐를 원래 큐에 추가 6. $인 경우를 찾아서 ans 에 1 추가 ✅Code from collections import deque import sys dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] # sys.stdin = open('D:/test.txt', 'r') def prin..

✅문제 ✅문제 풀이 외부에서 BFS를 한번 돌리고 죄수 2명을 기준으로 BFS를 한번씩 지나간 문의 수를 카운트해서 합치면 답이 나온다. 1. 외부에서 BFS를 돌리기 위해서 배열 바깥에 "." 문자열을 추가해서 실행시킨다. ex) 그럼 위에서 첫번째 테스트케이스의 경우 아래와 같이 배열이 실행된다. 2. 최단 경로는 3개의 배열의 위치가 같고 값이 같은 곳이다.(한 지점에 3개의 장소에서 최단거리로 도착했다는 의미) 3. 3경로가 같이 지나간 값을 전부 더해서 2번 더 중복됐으니 -2를 해주면 결과값이 나온다. ✅Code from collections import deque dx = [0,0,1,-1] dy = [1,-1,0,0] def bfs(a, x, y): n = len(a) m = len(a[0..