Dalin's Archive

문제 보러 가기 문제에 나와있는 뿌요 뿌요 룰을 그대로 구현하면 된다. 쭉 보면서 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있는지 보고 그런 그룹이 있으면, 뿌요들 터지게 하기 (단, 여러 그룹이 터져도 한 번의 연쇄만 추가됨) 남은 뿌요들이 중력의 영향을 받아서 떨어지게 하기 또 다시 1번으로 돌아가기 같은 색 뿌요가 상하좌우 4개 이상 연결되어 있는지 보는 것은 BFS로 했다. 중력의 영향받아서 잘 떨어지게 하는 것을 구현하는 게 어려웠다.ㅠ if와 while들을 이용해서 구현했다. 좀 복잡한 시뮬레이션, 구현도 연습해야겠다. 전에 풀었던 10703: 유성 문제가 떠올라서 비슷하게 하려고 했으나, 다른 점이 많아서 참고만 한 것 같다. import collections import sys inp..

백준 2468번 문제! 🔑코드와 설명 BFS로 풀었다. from collections import deque import copy #위, 아래, 오른쪽, 왼쪽을 체크하기 위해서 dx=[-1,0,1,0] dy=[0,1,0,-1] #입력 받기 n=int(input()) zone=[list(map(int,input().split())) for _ in range(n)] #가장 낮은 곳, 가장 높은 곳을 파악하려고 함 start=float('inf') #가장 낮은 곳의 높이 (사실 이 값은 사용하지 않음..) finish=-float('inf') #가장 높은 곳의 높이 for i in zone: for j in i: if j finish: finish=j safe_zone=[] #여..

백준 7569번 문제~ 😍 코드와 설명 BFS로 풀었다! import sys from collections import deque #앞뒤좌우상하를 봐야 하므로 dx=[-1,0,1,0,0,0] dy=[0,1,0,-1,0,0] dz=[0,0,0,0,1,-1] #입력받기 m,n,h=map(int,input().split()) tomato_zone=list(list(list(map(int,input().split())) for _ in range(n)) for _ in range(h)) #deque만들기 Q=deque() days=[[[0]*m for _ in range(n)] for _ in range(h)] #쭉 보면서 익은 토마토를 발견하면 모두 deque에 넣는다. for x in range(h): fo..

며칠 동안 고민 고민하고 많은 '틀렸습니다'와 '시간 초과'를 만났다.. 아직도 파이썬으로는 시간 초과가 나오지만... 파이썬으로 시간 초과 안 나오는 로직은 나중에 생각하기로 하고.. pypy로는 통과했다 !! 빙산 문제 보러 가기~~ 아이디어 ⭐ check 함수 -> 빙산이 두 부분 이상으로 나뉘었는지 체크 melt 함수 -> 1년마다 빙산의 각 구역을 물과 닿은 부분만큼 녹임(0까지만 녹임) all_melt 함수 -> 모든 빙산이 녹았는지 체크하는 함수 year = 0으로 초기화하고 시작 계속 빙산이 두 덩어리로 나뉘었는지 체크함. 1) 두 덩어리로 나뉘었으면 year을 출력하고 break 2) 두 덩어리로 나뉘지 않았으면 1-1) 빙산이 다 녹았으면(두 덩어리로 나뉘는..

문제 보러 가기~~ 아이디어 ✨ BFS인데 3차원 리스트를 활용해야 한다. 문제에서 3차원 리스트 쓰는 건 처음 해봤다 !! 일반적인 최단 거리 찾기에서 벽을 최대 한번 부술 수 있다는 조건이 추가되었다. 그래서 벽을 부수었는지 여부에 따라서 다른 2차원 리스트로 방문 체크를 해줬다. (즉 3차원 리스트를 만듦) 큐에 해당 인덱스, 벽을 부수었는지, 출발점부터 해당 위치까지의 거리를 넣어줬다. 큐 안에 요소가 있을 때, 하나씩 꺼내보면서 도착이면 그걸 따로 저장해줬고 그게 아니라면 4면을 돌아보면서 범위 이내인지 체크한다. 방문을 하지 않았고 벽인데, 아직 한번도 벽을 부수지 않았다면 벽을 부수고 거기로 간다. 방문을 하지 않았고 길이면, 벽을 부수지 않고 거기로 간다. '거기로 간다'라는..

문제로 GO! 전형적인 BFS를 활용했다. 다만 이동경로가 상하좌우나 대각선이 아니라서 특이했던 것 같다 ㅎㅎ import collections T = int(input()) # 한번 이동에 가는 경우들 directions = [(-2,-1),(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2)] for _ in range(T): l = int(input()) # 체스판 한 변의 길이 start_i, start_j = map(int,input().split()) final_i, final_j = map(int,input().split()) check = list([0]*l for _ in range(l)) # 거기까지 출발점에서 몇 번 이동했는지 체크 D = collect..

문제 보러 가기! 접근 💚 처음에는 소수가 나와서 어떻게 접근할지 고민했다. 우주 생명체 수 N에서 핑거 스냅으로 할 수 있는 4가지 일을 하고, 그게 A와 B 사이의 소수인지 매번 확인하는 것은 힘들 것 같았다. (매번 소수인지 쭉 계산을 해야 하니까.) 그래서 좀 생각을 바꿔봤다! A, B는 100000 이하니까 10만 이하의 소수를 모~두 구하는 것이다. (에라토스테네스의 체로 구했다.) 그리고 A 이상 B 이하의 소수들을 리스트에 저장해두고, 핑거 스냅으로 4가지 일을 한 후에 그 우주 생명체 수가 그 리스트의 값들 중에 있는지 보는 것이다. 최소 몇 번의 핑거 스냅을 해야 할지 구하는 것! 즉 최단 거리를 구하는 것과 같으니까 BFS로 풀었다. 4가지 일을 한 후의 우주 생명체 수를 보고 범위 ..

문제 보러 가기! 간단 문제 소개 ✅ 정수 s가 주어지는데, 이걸 t로 바꾸는 최소 연산 횟수를 구하는데, 가능한 방법을 출력해야 한다. s+s, s-s, s/s, s*s 연산을 사용할 수 있다. 바꿀 수 없는 경우도 존재한다. 아이디어 😄 최소 연산 횟수를 구하는 것이고, 가능한 방법이 여러 가지일 때 사전 순으로 앞서는 것을 먼저 출력해야 한다. => BFS 로 풀어야겠다고 생각했다. 그리고 s + s 는 2*s이고, s-s는 0이고, s*s는 s**2이고, s/s는 1이다. 이걸 좀 더 보다 보니까 -는 고려할 필요가 없다.라는 것을 알 수 있었다. 빼기하면 0이 되는데, t는 0보다 크다. 0이 되면 나누기는 불가능하고 더하기, 곱하기, 빼기해도 0이 된다. 그러니까 빼기를 해서는 전혀 답이 될 ..