ULISIA's Developer Life

출처 : 숨바꼭질 문제해석 BFS를 탐색을 통해서 큐에 들어갈 분기를 세가지로 나눈다. 현재좌표+1, 현재좌표-1, 현재좌표*2 다음좌표가 경계체크를 벗어나지 않고 한번도 방문한적이 없다면 이전좌표까지의 방문시간+1을 다음좌표까지의 방문시간에 갱신한다. 현재좌표가 K가 될때까지 걸리는 시간의 최적해를 구한다. 해답코드 #숨바꼭질 from collections import deque n, k = map(int, input().split()) MAX = 10 ** 5 isVisited = [0] * (MAX+1) def bfs(startX): q = deque() q.append(startX) while q: x = q.popleft() if x==k: return isVisited[x] for nx in ..

출처 : 영역 구하기 문제해석 모눈종이 전체 눈금을 0으로 초기화 한 뒤 사각형을 이루고 있는 부분을 1로 초기화해준다. 모눈종이 전체 눈금 한칸한칸을 탐색하는 기준으로 (0,0)부터 시작해서 흰색(0)을 이루고 있는 부분을 만나면 BFS/DFS 탐색을 시작함과 동시에 영역개수를 증가시킨다. 해당영역내에서 흰칸을 이루고 있는 부분만큼 영역넓이를 구해서 반환해준뒤 해당 넓이를 저장하는 리스트에 추가해준다. 최종적으로 구해진 영역 개수와 영역 넓이 리스트의 값들을 출력한다. 해답코드 import sys from collections import deque input = sys.stdin.readline n, m, k = map(int, input().split()) maps = [[0]*m for _ in ..

출처 : 미로 탐색 문제해석 대표적인 미로 탐색 유형의 쉬운 난이도 문제 미로 문제는 기본적으로 이동방향을 제어할 수 있는 배열이 자주 쓰인다. (2차원 기준 2방,4방,8방 등) y와 x좌표에 대한 변화량을 나타내는 dy,dx를 선언하여 각 방향별 인접배열 값을 탐색할 수 있다. dy = [-1,1,0,0] dx = [0,0,-1,1]주의할 점은 이동조건이 있는 미로탐색 등의 문제에서 항상 경계체크와 이동조건을 잊지 말아야 한다. 다음으로 탐색할 인덱스가 전체 맵 배열의 최소와 최대 인덱스 범위를 벗어나지 않는지, 해당 문제에서는 배열값이 1로 되어 있는곳에서만 이동이 가능하므로 해당 조건 또한 동시에 만족해야 한다. for d in range(4): ny, nx = y+dy[d], x+dx[d] if 0

출처 : 링크텍스트 문제해석 시간 가중치가 0과 1 둘로 나누어진다. 걷기 : x+1, x-1은 1초가 걸리고 순간이동 : 2*x는 0초가 걸린다. 단계가 이루어진다는 점으로 큐를 2개로 나눠 구현하는 방법이나 양방향 큐인 deque를 활용하여 2개를 별도로 만들지 않고, 순간이동할 경우 맨 앞에 추가, 걷기를 할 경우엔 뒤에 추가한다. 해답코드 #숨바꼭질 3 import sys from collections import deque MAX = 100001 isVisited = [False] * MAX time = [-1] * MAX input = sys.stdin.readline n, k = map(int,input().split()) q = deque() q.append(n) isVisited[n] =..

출처:5567번 결혼식 문제해석 N=동기의 수 상근이는 1번이므로 결과에서 포함되지 않음 친구와 친구의친구까지만 포함 1번 노드(상근이)를 시작으로 너비 우선 탐색(BFS)를 진행하면서 거리(dist)가 2 이하인 노드들의 개수만 세주면 된다. 해답코드 # 결혼식 import sys from collections import defaultdict, deque def bfs(start): ans=0 isVisited = [0 for _ in range(n+1)] isVisited[start] = 1 q = deque([[start,0]]) while q: u, dist = q.popleft() if dist