[백준][파이썬] 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. [백준][파이썬] 2206 벽 부수고 이동하기 - 메모리초과 BFS문제이지만 기존의 문제들과는 조금의 차이가 있다. 벽을 뚫을수 있다는 것을 체크해줘야한다. 1. 벽 뚫기를 위해 [x,y, 횟수] 이런식으로 저장을 해준다. 2. visited를 활용할때 주의할 점은 벽 안뚫기 / 벽 뚫었을때 따로 방문여부를 체크해줘야한다 (만약에 체크해주지 않으면, 벽뚫 vs 안뚫 이 만났을 때 오류가 생긴다 3. 메모리초과를 해결하지 못했다..... import sys import collections n, m = map(int,sys.stdin.readline().split()) map1 = [list(map(int,[*input()])) for k in range(n)] def recu(stack): stack.append([0,0,0]) cnt = 1 while stack.. 2020. 4. 13. [백준][파이썬] 3055번 탈출 -BFS 기본적인 BFS 문제에서 조금의 변형이 들어간 문제다. 처음 활용된 것은 물이라는 장애물도 퍼져나간다는것이다. 물 -> 길 ->물 ->길을 while안에서 활용했다 -항상 특정지점의 주변 모두를 한턴에 체크(FALSE)할때는 for(len(stack))구조로 활용해 주면 된다. -추가적으로 최단거리를 세기 위해서는 다른 리스트를 하나 더 만들어 수를 파악해주면 된다 import sys import collections n,m = map(int,input().split()) lit =[] ans =0 for i in range(n): tt = list(sys.stdin.readline()) lit.append(tt) dx = [0,0,1,-1] dy = [1,-1,0,0] def bfs(start,wate.. 2020. 4. 7. [백준][파이썬] 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. [백준][파이썬] 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 다음