코딩 공부

[1] 빙산이 2개의 덩이로 분리되거나 다 녹을 때까지 분리되지 않는다면 끝인 종료 조건을 생각한다.[2] 빙산이 있는 칸들은  BFS를 통해 각각 녹는 높이를 계산(사방 0인 칸의 개수)한다.from collections import dequedef bfs(si, sj): q = deque() q.append((si, sj)) visited[si][sj] = 1 candidates = [] while q: ci, cj = q.popleft() cnt = 0 for di, dj in ((-1, 0), (0, 1), (1, 0), (0, -1)): ni = ci + di nj = cj + dj ..

[1] 배열 arr을 만들고, 빈공간 '.'이 아닐 경우 bfs를 통해 같은 색의 뿌요들이 4개 이상 모여있는지 확인[2] 4개 이상 모여있을 경우, 뿌요들을 터뜨려 빈공간 '.'으로 변경 + 터진 이력이 있으므로 flag = True로 변경[3] 중[4] 터진 이력이 없을 경우, flag는 그대로 False이므로 연쇄 중단from collections import dequedef bfs(m, n): global flag q = deque() q.append((m, n)) temp = [(m, n)] # 같은 색깔 연결 정보 visited[m][n] = 1 # 방문 처리 주의! while q: ci, cj = q.popleft() for di, d..

1. 어차피 뱀과 사다리는 서로 정확히 겹치는 경우가 없으므로 시작과 끝이 Key - Value로 정해져 있는 것과 마찬가지이므로 info라는 dictionary를 만들어줘서 관리한다.2. 만일, 뱀이나 사다리를 타고 이동했을 때 방문했던 곳이라면 무한 반복이 가능하므로 visited라는 방문 배열을 하나 만들어 관리한다.3. BFS방법을 이용해 1~6칸을 이동하는 주사위 굴리기의 최솟값을 구할 수 있을 것 같다.from collections import dequedef bfs(): q = deque() q.append(1) # 1번 칸에서 시작 cnt = 0 # 주사위 굴리는 횟수 while q: cnt += 1 for _ in range(len(q)): ..

항상 테두리 부분은 공기이므로 항상 (0, 0)을 시작으로 BFS를 돌린다. 시간이 얼마나 걸리는가를 구하기 위해 count라는 변수로 세주고 무한 while문을 돌려준다. BFS를 돌리면서 치즈를 만나면 치즈라는 리스트에 x, y좌표를 넣어주고 q에는 넣어주지 않는다. 공기를 만나면 q 안에 (x, y)를 넣어줌으로써 계속 q를 돌린다. 이때 cheese에 저장되는 정보가 없으면 무한 반복문을 빠져나가도록 하고 그렇지 않으면 cheese개수 정보를 갱신해주고 가장 테두리 치즈 정보를 담고 있는 치즈 리스트에서 좌표를 꺼내며 공기(arr[x][y]==0)으로 바꿔준다. from collections import deque def bfs(): global answer# 가장 마지막에 남는 치즈 갱신 위함 ..

인구이동이 없을 때까지 진행하므로 while True의 무한 반복문 속에서 횟수를 세야겠다. bfs를 통해 연합이 이루어질 수 있는 칸들을 묶고 합산을 칸수로 나눔으로써 인구 수를 재배치시킨다. 이때, 연합의 수가 자기자신뿐이라 1개라면 재배치 및 인구 이동으로 치지 않도록 유의한다. 인구 이동(flag)이 없다면 break문을 통해 반복문에서 빠져나온다. from collections import deque def bfs(x, y, num): global flag q = deque() q.append((x, y)) union = [(x, y)]# 연합할 칸들의 정보 리스트 visited[x][y] = 1 people_sum = num# 연합할 칸들의 인구 수 총합 while q: ci, cj = q.p..

빈 칸인 공간들 중에 3칸을 뽑아서 벽을 만들기 위해 DFS를 이용한다. DFS의 효율을 높이기 위해 지금 선택한 벽의 개수가 3을 넘어가면 가지치기를 실행해준다. 3개의 후보를 뽑았다면, 3개의 후보를 벽 상태인 1로 만들어주고 BFS를 통해 바이러스를 퍼뜨리고 전체 연구실의 크기(N*M)에서 벽의 수(wall), 임시 벽(3), 바이러스가 퍼진 칸(len(virus)+count)을 빼주면 안전 영역의 크기를 구할 수 있어 이를 return 한다. 위의 과정에서 return 받은 값을 이용해 answer의 값을 안전 영역의 최댓값으로 갱신한다. 임시 벽을 다시 0인 상태로 되돌려준다. from collections import deque def dfs(n, lst): global answer if le..