남남이루의 고군분투 🌳

문제 토마토 익으려면 얼마나 걸려? 주의 : pypy로 해야지만 시간 초과가 안떴다. 난이도 : 다시보니, 훨 이해가 잘간다! import sys from collections import deque sys.stdin = open('./BFS/input2.txt','rt') input = sys.stdin.readline m,n = map(int, input().split()) g = [list(map(int, input().split())) for _ in range(n) ] queue = deque([]) # 1 한 놈 queue에 넣고 시작 for i in range(n): for j in range(m): if g[i][j] == 1: queue.append([i,j]) # print(queue)..

import sys sys.stdin = open('input.txt', 'rt') input = sys.stdin.readline # g[h][w] # w 열의 개수, # h 행의 개수, dx = [1,-1,0,0,1,-1,1,-1] dy = [0,0,1,-1,1,-1,-1,1] def DFS(x,y): global comp if 0

원리 텀프로젝트처럼 사이클 돌리고 그 길이랑, 그 길이 아닌거(포함 미포함)랑 구해서 최대값 구했는데 자꾸 사이클이 엄청나게 길어짐.. ㅇㅅㅇ # 두 번째 줄에 n개의 정수 xi (i = 1, 2, ... , n, 1 ≤ xi ≤ n) 가 순서대로 주어진다. xi는 xi번째 사람이 버스에 타지 않는다면 i번째 사람 역시 버스에 타지 않음을 의미한다. # 얘는 꼭 타야돼 import sys sys.stdin = open('in2.txt') sys.setrecursionlimit(10**5) input = sys.stdin.readline n, cap = map(int, input().split()) graph =[0] + list(map(int, input().split())) check = [False]..

(+) 이차원 배열의 max 찾기 방법 1. graph = [list(map(int, input().split())) for _ in range(N)] graph_min = min(map(min, graph)) # min_height graph_max = max(map(max, graph)) # max_height 방법 2. g = [] largest = 0 for _ in range(n): l = list(map(int, input().split())) largest = max(max(l),largest) g.append(l) 문제 영역 구하는 문제인데, 물의 수위를 조절하며 영역의 개수가 최대일 때를 찾아야 한다. 예시 답은 다 맞게 나오는데, 백준 저지에서 자꾸 틀린다... 왜지... 근데 왜 틀렸..

경로 찾는 문제, 방향이 있는 그래프 문제이다. DFS 선언 내부 for 문은 매개변수 v행 에 호응하는 열i 에 해당한다. 행 단위로 확인하기 때문에 visit이 2차원이 아니다. 또 visit을 반복문 내에서 출력하는 게 다른 DFS와의 차이점이다. 간단하지만 아직 연습이 더 필요한 문제이다. import sys sys.stdin = open('graph input.txt', 'rt') input = sys.stdin.readline size = int(input()) visit = [0 for i in range(size)] g = [list(map(int, input().split())) for _ in range(size)] def DFS(v): for i in range(size): if vi..

문제 : 그래프에서 사각형 좌표 입력받으면, 사각형을 제외한 부분의 넓이와 개수를 구하라 포인트 1. 좌표값과 행렬의 차이 2. DFS 3. 좌표값 두개로 사각형 그리기 xy 좌표따라 그래프 그리는 거에서 좀 걸렸다. 넓이까지 구하는 게 아니었으면 더 빨리 풀 수 있었는데, 넓이 구해야 돼서 범위를 모퉁이 +1 없이 정확하게 구해야해가지고 더 오래 걸렸다. 대신에 영역 연습, 행과 열 변수 연습에 좋았다.. import sys sys.setrecursionlimit(10**4) input = sys.stdin.readline m,n,k = map(int, input().split()) g = [[0]*(n) for _ in range(m)] for _ in range(k): # x y x y lx,ly,..

import sys sys.stdin = open('graph input.txt', 'rt') input = sys.stdin.readline size = int(input()) graph = [list(map(int, input().rstrip())) for _ in range(size)] print(graph) apt = [] dx = [1,-1,0,0] dy = [0,0,1,-1] def DFS(x,y): global cnt if 0 탐색 시간복잡도 단지수(V) : N**2 연결(E) : 4*N**2 O(V+E) : 5N**2 => N*2 => 25\*2 => 625 : 2억보다 작음 자료구조 리스트? visited => graph 문제 접근하는 루틴을 연습해봤다. 추가..

문제 가장 큰 대륙을 찾으면 된다. 음쓰 한번에 많이 모여져 있는거 max값 출력. 초기 코드 import sys sys.stdin =open('in.txt','rt') input = sys.stdin.readline sys.setrecursionlimit(10**6) # 재귀함수 깊이 제한 풀기 dx = [1,-1,0,0] dy = [0,0,1,-1] def DFS(x,y): cnt = 1 for i in range(4): xx = x+dx[i] yy = y+dy[i] if xx n or yy > m: return cnt if g[xx][yy] == 1: cnt+= DFS(xx,yy) g[xx][yy] = 0 return cnt # n 세로길이, m 가로길이, k..

그래프 탐색하면서 한 구역인 애들 묶으면 총 몇 구역인지 세는 문제다. 아 행렬 위치가 너무 헷갈린다. graph[x][y]랑 가로m, 세로n이 너무 헷갈려서 index에러 때문에 고생했다. 우선, 문제의 함정인 행과 열, 가로와 세로 에 대해서 서술하고, 왜 이 문제를 다른 분들의 답코드를 봤음에도 1시간 이상이 걸리며 return한테 혼쭐난 과정을 자세하게 풀어보겠다. 행과 열, 가로와 세로 matrix = [[a,b,c],[A,B,C]] 가 있다고 하자. 이 이차원 배열을 각각 다른 말로 표현해보겠다. 배열 표현하기 2행 3열의 배열 가로 길이 3, 세로 길이 2의 좌표 0 >> 정답, 사실상 1try와 같아야 한다고 생각했는데 정답. 머리가 먼저냐 꼬리가 먼저냐라서 결과가 다르게 나오면 안된다. ..

문제 양방향 그래프의 연결 요소를 구하는 문제로, DFS의 대표적인 유형의 문제 중 하나이다. 풀이 DFS는 소스코드 프레임에 아래와 같은 것들이 자주 쓰인다. visted = [False]*(n), count = 0, graph = [[] for _ in range(n)] 첫 번째 visited는 노드를 방문했는지 확인하기 위함이고, 두 번째는 문제에서 요구하는 것을 count, 마지막은 graph이다. 그래프의 특성에, 방향이 없다고 했기 때문에, 그래프 생성할 때 인덱스와 값을 switch해서 두번 씩 적어줘야 한다. for i in range(m): u, v = map(int, input().split()) graph[u].append(v) graph[v].append(u) DFS를 최초로 호출하..