나의 개발일지

문제 : https://www.acmicpc.net/problem/2638 BFS from collections import deque n, m = map(int, input().split()) Map = [list(input().split()) for _ in range(n)] cnt = 0 for i in range(n): # 치즈 개수 세기 for j in range(m): if Map[i][j] == '1': cnt += 1 def bfs(): Q = deque([[0, 0]]) visit = [[0] * m for _ in range(n)] cheese = [[0] * m for _ in range(n)] while Q: zx, zy = [0, 0, 1, -1], [1, -1, 0, 0] x, ..

문제 : https://www.acmicpc.net/problem/7576 BFS deque의 popleft()를 쓰지않고 pop(0)으로 했을 때 시간초과가 뜬다. from collections import deque n, m = map(int, input().split()) tomato = [] for i in range(m): tomato.append(list(map(int, input().split()))) Q = deque([]) zero = 1 for i in range(m): # 4 for j in range(n): # 6 if tomato[i][j] == 1: # 익어있는 토마토들의 위치를 먼저 큐에 저장 Q.append([i, j]) if tomato[i][j] == 0: # 안익은게 있..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/43163 DFS / BFS BFS 방식을 선택 from collections import deque def solution(begin, target, words): answer = 0 q = deque() q.append([begin, 0]) # 시작 단어와 깊이 V = [ 0 for i in range(len(words))] # 방문 배열 while q: word, cnt = q.popleft() if word == target: # 타겟과 같은 단어면 멈춤 answer = cnt break for i in range(len(words)): temp_cnt = 0 if V[i] == 0: ..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/87694 겹치는 사각형들의 테두리만 잘 표현하면 BFS 구현만으로 풀 수 있다. 키 포인트 : 사각형의 크기를 2배로 늘린다. 사각형들의 크기를 2배로 키우는 이유는 꺾이는 부분에서 문제가 생기기 때문이다. from collections import deque def solution(rectangle, characterX, characterY, itemX, itemY): map = [[0] * 102 for _ in range(102)] # 사각형을 2배 크기로 그리기 위해 2배정도 늘린 맵 visit = [[0] * 102 for _ in range(102)] # 방문 체크, 거리 체크 f..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/49189 큐를 이용한 BFS로 구현 풀면서 '게임 맵 최단거리' 문제와 비슷하다고 생각이 들어서 거의 같은 방식으로 구현했다. from collections import deque def solution(n, edge): graph = {i:[] for i in range(1, n+1)} # n 개의 빈 리스트를 가진 딕셔너리 생성 (1:[], 2:[]...) visit = [0] * (n + 1) # 방문 체크 및 거리 확인 리스트 visit[1] = 1 # 시작 지점은 1로 지정 for key, value in edge: # 양방향으로 연결된 노드들 표현하는 그래프(딕셔너리) graph[..