cmod.ify

초안메모리 초과가 난 코드10억개의 메모리를 생성하려고해서 메모리 초과가 났다 BFS로 만들었었다.import sysfrom collections import dequeinput = sys.stdin.readlineA, B = map(int, input().strip().split())num = [sys.maxsize for _ in range(B + 1)]answer = -1q = deque([A])num[A] = 1while q: cur = q.popleft() # 정답인지 검사 if cur == B: answer = num[cur] break # *2를 했을 때 b보다 안커지는지 검사 elif cur > B: q.popleft() ..

처음에 bfs인가 싶었는데 또 완전탐색인가 싶기도 했음결국 모르겠어서 확인하니까 bfs가 맞았음..제미나이의 도움을 받았다.미로탐색이나 토마토 같은 정석의 큐브가 아니라 감이 안 온 문제였다. 문제 이해를 위한 설명을 이렇게 해줬다.1. BFS는 '동심원'이 퍼져나가는 것과 같습니다미치광이 주사위 도박사가 1번 칸에 서서, 한 번에 분신술을 써서 6명을 만든다고 상상해 보세요.0초 (시작): 1번 칸에 나 혼자 있음. (큐: [1])1초 (첫 번째 주사위): 내 분신 6명이 주사위 1, 2, 3, 4, 5, 6을 들고 각각의 칸으로 달려갑니다.만약 3번 칸에 사다리가 있다면? 3번으로 간 분신은 즉시 사다리 끝인 20번 칸으로 순간이동합니다.이제 1초 뒤에 분신들이 서 있는 곳들은 [2, 20, 4, 5..

초안bfs를 두개 만들기 귀찮아서 한 색을 다 r로 바꿔버림근데 다른 문법적 실수 때문인 가 싶어서 결국 bfs 다시 만듦근데 그냥 방문처리 잘 못했던 실수였다.그래서 두 번 푼 사람이 되어버렸음 ㅠㅠimport sysfrom collections import dequeinput = sys.stdin.readlinen = int(input())color = []for i in range(n): l = input().strip() color.append(l)visited = [[False] * n for _ in range(n)]dx = [-1, 1, 0, 0]dy = [0, 0, -1, 1]flag = ""def bfs(x, y, col): cnt = 0 q = deque([(x, ..

4방향 탐색 토마토는 풀어봤는데 6방향은 처음 풀었다. 3차원 리스트도 처음 만들어봐서 머릿속으로 도저히 그려지지 않아 그림판까지 사용했다 ㅋㅋdx, dy말고 dz까지 추가됐다. 초안import sysfrom collections import dequeinput = sys.stdin.readlineM, N, H = map(int, input().split())tom = []# 입력 받을 때 0 개수 세기.zerocnt = 0for i in range(H): tmp = [] for j in range(N): li = list(map(int, input().strip().split())) if 0 in li: zerocnt = 1 tmp.a..

그냥 제출 했는데 틀려서 뭐지 하고 다시 글 봤더니 정렬해서 출력해야 했다앗차차 글을 잘 읽도록 하자 import sysfrom collections import dequeinput = sys.stdin.readlinen = int(input())gra = []for i in range(n): li = input().strip() li2 = [int(i) for i in li] gra.append(li2)dx = [0,0,-1,1]dy = [-1,1,0,0]visited = [[False] * n for _ in range(n)]def bfs(x, y, cnt): q = deque([(x,y)]) visited[x][y] = True while q: cx, c..

bfs 하는데 처음에 pop했다가 틀림popleft라는 것을 잊지말자 import sysfrom collections import dequeinput = sys.stdin.readlinen,m = map(int, input().split())miro = []visitied = [[False] * m for _ in range(n)]for i in range(n): li = input().strip() li2 = [int(i) for i in li] miro.append(li2) # 1 이동 가능 , 0 이동 불가# 1,1위치부터 n,m위치로 이동하는 최소칸수(bfs)dx = [0,0,-1,1]dy = [-1,1,0,0]def bfs(): x,y,cnt = 0,0,1 q =..

import sysfrom collections import dequeinput = sys.stdin.readline# 입력n, m = map(int, input().split())# 초기화friends = [[] for i in range(n+1)]Min = sys.maxsizeanswer = 0# 관계 입력 for i in range(m): a, b = map(int, input().strip().split()) # 양방향 friends[a].append(b) friends[b].append(a)# 정렬for f in friends: f.sort()def bfs(i,j): # i = 나, 0 = 거리 q = deque([(i, 0)]) visited..

문제 이해 1이면 가고 2면 출발 0이면 벽임 못 도달 하는 곳은 -1로 출력 해야함 그럼 모든 곳을 -1로 초기화하고 나머지는 거리를 이전거리에서 하나씩 더하면 될 것 같음 출력 예시 보니까 bfs인 것 같음. 입력값보니까 dfs하면 어차피 시간초과임 ======================================== 코드 계획 입력 받기 N, M 저장 N 번 반복하면서 입력 받는데 2부터 탐색 해야 하니까 저장(x,y) 네방향 이동할 dx, dy 리스트 생성 -1로 초기화한 answer 배열 생성 방문 여부 visited 배열은 False로 초기화 큐에 2의 x,y좌표 저장 방문처리 answer 처음위치 0으로 정하기 q가 비어있지 않을 동안 반복 curx, cury에 q pop해서 저장 네 ..

bfs, dfs, 네방향 탐색 모두 c++로만 해보고 파이썬으론 처음 해봤다기억도 가물가물해서 1260을 먼저 풀고 왔다근데 네방향은 또 새로운 느낌 ㅎㅎ; dfs 로 풀었는데 생각해보니까 시간초과가 날 수 밖에 없는..경로를 구하는 문제가 아니라면 bfs로 무조건 생각해야지 c++에선 queue 쓰는게 쉬웠는데 여긴 좀 헷갈린다import collections from deque# 삽입 시 []로 묶어줘야 한다q = deque([data])# 앞에 데이터를 뽑을 시q.popleft() 문제 풀 때 헷갈렸던 점1. 입력 받을 때 strip() 처리2. 방문 처리 : 맵 안쪽인지 확인하고 visited로 방문했는지 확인 만약 x가 아니라면(o와 p는 방문 가능하다) 방문처리하기 q에 위치 저장하기..