코딩 공부

항상 테두리 부분은 공기이므로 항상 (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# 가장 마지막에 남는 치즈 갱신 위함 ..

파이어볼의 정보를 담을 리스트 fireballs를 만들고 각각의 파이어볼 정보를 fireballs에 저장하고 파이어볼들을 arr에 위치시킨다. fireballs에 담겨있는 파이어볼의 정보를 pop으로 하나씩 꺼내 다음 좌표를 구한다. 이때 좌표의 양끝, 즉 위와 아래, 오른쪽과 왼쪽이 이어지는 좌표 특성이 있음에 유의한다. 따라서 파이어볼의 위치를 N으로 나눠준다. (모든 fireballs의 다음 좌표를 구하고 나면, fireballs는 빈 리스트 상태가 된다.) 모든 좌표를 돌면서 하나의 파이어볼만 있는 좌표는 fireballs 리스트에 그대로 넣어준다. 2개 이상의 파이어볼이 있는 좌표는 문제에 따라 총질량, 총속력 등을 구해 생성될 파이어볼들의 질량과 속력을 구한다. 이때 총질량//5 == 0 이 ..

행과 열의 길이에 따라 R연산과 C연산이 정해지므로 현재 배열의 행과 열의 길이를 계속 알고 있어야 한다. 또한, 연산에 따른 배열의 최대 길이에 따라 0을 붙여줘야하므로 최대길이를 연산마다 구해야 한다. 각 행마다 수와 수의 등장 횟수를 구하기 위해 info라는 딕셔너리에 "key=수, key값=등장횟수"를 저장한다. 이때 수가 0이라면 info라는 딕셔너리에 넣지 않도록 주의한다. 수의 등장 횟수가 커지는 순으로, 수가 커지는 순으로 정렬을 한다. 최대 길이에 맞춰 각 행 끝에 0을 붙여준다. row와 column의 수를 재정의해주고, 바뀐 배열을 갱신해준다. C연산의 경우, 위의 과정을 반복하기 전에 배열을 R연산의 배열 형태로 바꿔주고 연산을 진행한다. 조건에 맞을 경우 break를 해주는데 이때..

공기청정기의 좌표에 의해 위쪽의 순환 및 아래쪽의 순환이 이루어지므로 공기청정기의 좌표를 따로 구해놓는다. T번의 반복이 이루어지므로, 반복문 안에서 확산 및 순환을 구현한다. 미세먼지의 확산은 모든 칸에서 동시에 일어나므로 plus라는 하나의 배열을 임시로 만들어 확산될 먼지들의 합을 구해준 후, 원래의 배열인 arr에 plus값들을 모두 더해준다. 위쪽 순환과 아래쪽 순환을 일으키는데, 위쪽 순환의 경우 시계 방향으로 돌며 배열의 값을 서로 바꿔주고, 아래쪽 순환의 경우 반시계 방향으로 돌며 배열의 값을 서로 바꿔준다. 순환이 끝난 후, 공기청정기의 처음 나가는 칸은 항상 먼지가 없으므로 0의 값으로, 원래 공기청정기의 칸은 -1의 값으로 대입해준다. 모든 칸의 먼지의 양을 더해준다. R, C, T ..

인구이동이 없을 때까지 진행하므로 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..