[백준][파이썬] 3190 :뱀 [핵심] 1. 뱀의 형태를 deque로 저장하기 처음에 True false 맵으로 뱀의 상태를 저장하려 했으나, 뱀의 움직임을 고려하는것이 매우 복잡했다. FIFO 이러한 형태의 문제를 잘 기억할것 2. if 와 elif는 다르다. if와 elif의 차이를 정확히 기억하자(이것때매 오류 발생) -다시 검토하고 싶을 땐 if 두번 -다시 검토 아닐때 if , eilf 3. time을 언제줄지도 중요! from collections import deque num = int(input()) map1 = [[0 for i in range(num)] for j in range(num)] gogo = deque() capple = int(input()) # 사과의 수 #dchange = [] # 사과 저장 for .. 2020. 4. 28. [백준][파이썬] 11403번: 경로찾기 BFS문제 BFS 문제인 이유: 인접 행렬들을 하나씩 True 해나가는 과정이기떄문. 사실 DFS로 풀어도 될것같긴하다 어차피 False처리를 계속 해주기때문에 메모리나 시간에 있어서도 비슷할것 같다는 생각이 든다. 핵심은 1. 초기값 dfs안에 한번에 stack변수에 저장(배추문제에서도 했다.) 2. collection 이용하여 시간단축 복잡하지 않은 문제였다. import collections num = int(input()) lit =[] visited = [[False for i in range(num)] for j in range(num)] for i in range(num): t = list(map(int,input().split())) lit.append(t) def dfs(stack): stack =.. 2020. 4. 2. [백준][파이썬] 7569 토마토(2) - 3차원 [핵심] 3차원 리스트를 활용하고 index를 맞게 조절해주느라 조금 헷갈렸다. 나는 기본적으로 z축을 먼저 정렬하여 [z][x][y]구조로 생각했다. 최단거리 문제는 BFS가 어울린다. 왜냐하면 동시에 카운팅을 해주어야 하니까. *한번에 stack를 모두 처리하기 위해 while안에 포문을 한번더 설정해준것. *초기값 모두 한번에 해결하기 위해 dfs안 while밖에 포문으로 stack에 넣어준것 이 핵심이였다. 꼭 반복 연습하자 import collections #dq를 활용 m,n,h = map(int,input().split()) total =[] for i in range(h): lit =[] for j in range(n): t = list(map(int,input().split())) lit.. 2020. 4. 1. [백준][파이썬] 2178 미로탈출 (최단거리) 처음에는 DFS문제라고 생각했다. 미로를 찾아가면서 결국 (M,N)에 도착한 값들을 list에 넣어주고 정렬시켜준다음에 최소값을 찾으면 되니까!! 결과는 잘 나왔다. 하지만 시간초과가 났다. 이런 최단거리 문제를 푸는 방법은 BFS라고 한다. 처음에 어떻게 하면 최단길을 찾을 수 있을지 고민했다. (왠지 동적프로그래밍에 더 가까워지는듯한....) 답은 생각보다 간단했다. 모든 블록에 값을 넣어주는것..(수학 문제풀떄랑 비슷했다.) 사용한 리스트가 꽤 많았다. visited - 방문여부 파악을 위해 사용 lit - 기존의 정보가 담겨있는 리스트 추가로 거리를 담아주는 리스트가 사용되었다. dlog- 흔적을 남기는 배열이다. DFS는 주로 재귀함수와 스택을 BFS는 주로 while문과 큐를 사용한다. n,m.. 2020. 3. 30. [파이썬]DFS BFS 연습할 기본 코드 def dfs(v): print(v, end=' ') visit[v] = 1 for i in range(1, n + 1): if visit[i] == 0 and s[v][i] == 1: dfs(i) def bfs(v): queue = [v] visit[v] = 0 while (queue): v = queue[0] print(v, end=' ') del queue[0] for i in range(1, n + 1): if visit[i] == 1 and s[v][i] == 1: queue.append(i) visit[i] = 0 n, m, v = map(int, input().split()) s = [[0] * (n + 1) for i in range(n + 1)] visit = [0 for i in ran.. 2020. 3. 29. [백준][파이썬] 2606 바이러스(DFS-Depth First Search) 사실 3번째 도전이였다.. 처음 DFS가 잘 모르는 상태에서 문제를 풀려고 했을때, 너무 어렵게 느껴졌고 DFS 개념을 보고 다시 문제를 풀려했을때도 어려웠다. 근데 분할정복, N과M 시리즈, 별찍기를 풀고 DFS 기본문제인 배추문제와 텀프로젝트 문제를 풀고 다시 돌아왔더니 너무 쉽게 풀려서 당황했다. 역시 지금 단계(실력)에서는 많은 고민 보다는 코드의 구조를 공부하고 변형하는 연습을 많이하는것이 실력 상승에 도움이 될것같다. num = int(input()) case = int(input()) lit = [[0 for i in range(num)] for j in range(num)] for i in range(case): x,y =map(int,input().split()) lit[x-1][y-1].. 2020. 3. 29. [파이썬][백준] 2667 단지번호 붙이기 [핵심] 배추문제랑 거의 동일한 문제 차이점은 수를 하나더 카운팅 해주는것뿐 While문을 활용한 del 기억하자!!! num = int(input()) lit = [] dx = [0,0,1,-1] dy = [1,-1,0,0] ans =[] cot =[] def recu(x,y): cnt = 0 stack = [[x,y]] while stack: x = stack[0][0] y = stack[0][1] del stack[0] cnt+=1 lit[x][y] = '0' for i in range(4): X = int(x)+dx[i] Y = int(y)+dy[i] if 0 2020. 3. 28. [백준][파이썬] 1012 유기농 배추 BFS [핵심] BFS 분류되는 이유는 결국 1과 붙어있는것들을 모두 제거할때 count가 증가하기떄문이다. 연습해야할 코딩 방식 1. dx dy를 이용한 좌표처리 그리고 경계값 -1일때 인덱스 에러 안나게 범위 설정해주는것 2. 재귀함수를 이용한것이 아니라 While문으로 활용 3. [0]*n으로 배열을 만들면 이상하게 다르게 값이 출력된다.. (이유는 아직 모름) 주소값을 공유하는 개념때문인가? 여러번 코딩해서 구조 익힐것 numcase = int(input()) dx = [-1,0,0,1] dy = [0,1,-1,0] def recu(x,y): check = [[x,y]] while check: checka = check[0][0] #x,y값 저장 checkb = check[0][1] del check[0.. 2020. 3. 26. 이전 1 다음