컨텍스트는 사용자와 다른 사용자, 혹은 사용자와 시스템 또는 디바이스 간의 상호작용에 영향을 미치는 사람, 장소, 개체 등의현재 상태를 규정하는 정보들이다.
OS에서의 컨텍스트는CPU가 해당 프로세스를 실행하기 위한 해당 프로세스의 정보들이다.
이러한 컨텍스트는 프로세스의PCB(Process Control Block)에 저장된다.
PCB(Process Control Block)
PCB란 운영체제가프로세스에 대한 중요한 정보를 저장해 놓을 수 있는 저장 장소를 뜻한다.
PCB는 프로세스 생성 시 만들어지며 주기억장치에 유지된다. 프로세스 상태 관리와컨텍스트 스위칭을 위해 필요하다.
위 이미지는 PCB의 정보 저장 구조에 관한 이미지이고 PCB에는 다음과 같은 정보가 저장된다.
프로세스 상태: 생성, 준비, 수행, 대기, 중지
프로그램 카운터: 프로세스가 다음에 실행할 명령어 주소
레지스터: 누산기, 스택, 색인 레지스터
프로세스 번호
Context Switching(문맥교환 / 콘텍스트 스위칭)
컴퓨터가 매번 하나의 Task만 처리할 수 있다면?
=> 해당 Task가 끝날 때까지 다음 Task는 기다려야 함
=> 그렇다면 매우 느린 속도 때문에 사용하기 불편할 것.
이를 해결하기 위해 Context Switching이 등장.
다양한 사람들이 동시에 사용하는 것처럼 하기 위해서는 빠른 속도로 Task를 바꿔 실행해 실시간처럼 보이도록 해야 했고, CPU가 Task를 바꿔가며 실행하기 위해 Context Switching이 필요하게 되었다.
또한 새로 실행되는 Task가 아니라면 이전에 실행될 때 레지스터들이 지니고 있던 데이터들을 불러와서 이어서 실행해야 하므로 컨텍스트 스위칭이 필요하게 되었다.
Context Switching이란 멀티프로세스 환경에서 CPU가 하나의 프로세스를 실행하고 있는 상태에서인터럽트 요청에 의해다음 우선순위 프로세스가 실행돼야 할 때 기존의 프로세스의 상태 또는 레지스터 값(Context)을 저장하고 CPU가 다음 프로세스를 수행하도록 새로운 프로세스의 상태 또는 레지스터 값(Context)를 교체하는 작업이다.
Context Switching의 순서
이미지 출처 : https://velog.io/@underlier12/OS-17-%EC%BB%A8%ED%85%8D%EC%8A%A4%ED%8A%B8-%EC%8A%A4%EC%9C%84%EC%B9%AD-%EC%A0%95%EB%A6%AC
실행 중지할 프로세스 정보를 해당 프로세스의 PCB에 업데이트하여 메인 메모리에 저장
다음 실행할 프로세스 정보를 메인 메모리에 있는 해당 PCB 정보를 CPU에 넣고 실행
Context Switching의 단점
프로세스가 변경되는 과정에서 데이터를 서로 백업하기 때문에CPU의 과부하가 생길 수 있다.
중앙처리장치(CPU)는 명령어의 해석과 자료의 연산, 비교등의 처리를 제어하는 컴퓨터 시스템의 핵심장치이다.
다양한 입력 장치로부터 정보를 입력받아 처리한 후, 그 결과를 출력장치로 보내는 일련의 과정을 제어하고 조정하는 일을 수행한다.
CPU는 사람의 두뇌와 같이 컴퓨터의 모든 시스템을 제어, 처리하는 가장 핵심적인 장치라고 할 수 있다.
CPU의 구성요소
이미지 출처: https://mk28.tistory.com/15
CPU는 크게제어 장치, 연산 장치(ALU), 레지스터 와 각 구성 요소를 연결하는 내부 버스로 구성되어 있다.
1. 제어 장치 (CU, Control Unit)
컴퓨터 시스템의 작동을 통제하고 지시하는 장치
기억 장치로부터 프로그랭 명령을 순차적으로 꺼내 해독하고, 해석에 따라서 명령어 실행에 필요한 제어 신호를 기억장치, 연산장치, 입출력 장치 등으로 보내는 장치
프로그램 카운터(PC), 명령 해독기, 부호기, 명령 레지스터 등으로 구성된다.
2. 연산 장치 (ALU, Arithmetic and Logical Unit)
명령어를 실행하기 위한 마이크로 연산을 수행하는 장치
연산에 필요한 자료를 입력받아 산술, 논리, 관계, 이동(Shift) 등 다양한 연산을 수행하는 장치
가산기, 보수기, 누산기, 데이터 레지스터 등으로 구성된다.
3. 레지스터 (Register)
CPU(중앙 처리 장치)내에 있는 소규모의 고속 기억장치
명령어 주소, 코드, 연산에 필요한 데이터, 연산 결과 등을 임시로 저장한다.
레지스터는 메모리 계층의 최상위에 위치하며 가장 빠른 속도로 접근 가능한 메모리이다.
용도에 따라 범용 레지스터와 특수 목적 레지스터로 구분됨
특수 목적 레지스터의 종류
MAR (메모리 주소 레지스터) : 읽기와 쓰기 연산을 수행할 주기억장치 주소를 저장
PC (프로그램 카운터) : 다음에 실행될 명령어의 주소를 저장
SP (스택 포인터) : 스택의 최상위 주소를 저장
IX (인덱스 레지스터) : 인덱스 주소 지정 방식에서 인덱스를 저장
IR (명령어 레지스터) : 명령어를 호출해서 해독하기 위해 현재 명령어를 임시로 저장
MBR (메모리 버퍼 레지스터) : 주기억장치의 내용을 임시로 저장하는 역할
AC (누산기) : 산술 논리 장치의 연산 결과를 임시로 저장
PSR (프로그램 상태 레지스터) : CPU의 현재 상태 정보를 저장
CPU의 연산
CPU의 연산 순서는Fetch->Decode->Execute->Writeback으로 이루어지며 각 과정의 설명은 다음과 같다.
1. Fetch(인출): 메모리상의 프로그램 카운터(PC)가 가리키는 명령어를 CPU로 인출하여 적재
2. Decode(해석): 명령어의 해석. 이 단계에서 명령어의 종류와 타겟 등을 판단한다.
3. Execute(실행): 해석된 명령어에 따라 데이터에 대한 연산을 수행한다.
4. Writeback(쓰기): 명령어대로 처리 완료된 데이터를 메모리에 기록한다.
CPU의 동작 과정
(1) 보조기억장치에서 저장된 프로그램을 읽거나, 입력장치에서 입력받은 데이터를 주기억장치에서 읽는다.
(2) 주기억장치에서 읽어온 데이터를 중앙처리장치(CPU)가 읽고 처리한 후 다시 주기억장치로 보낸 후 저장한다.
(3) 주기억장치는 연산된 데이터를 출력장치에 보내거나 보조기억장치에 저장한다.
(4) 제어장치는 (1)-(3) 과정에서 명령어가 순서대로 잘 실행되도록 제어하는 역할을 수행한다.
CPU의 명령어
명령어 세트
연산 코드 (OP Code) | 피연산자 (Operand)
명령어 세트는 CPU가 실행할 명령어의 집합이다.
명령어 세트는 실행할 연산을 나타내는연산 코드 (Operation Code)와 연산에 필요한 데이터나 데이터의 저장 위치를 나타내는피연산자 (Operand)로 구성된다.
연산 코드 (Operation Code)
연산 코드는 실행하는 연산의 종류에 따라 다음과 같이 네 가지 기능으로 나뉜다.
연산 기능: 사칙연산, 이동(shift), 보수 등의산술연산과 논리곱, 논리합, 부정 등의논리연산을 수행한다.
제어 기능: 조건 분기와 무조건 분기 등을 사용하여명령어의 실행 순서를 제어한다.
데이터 전달 기능: 레지스터와 레지스터 사이, 레지스터와 주기억장치 사이에서데이터를 전달한다.
입출력 기능:프로그램과 데이터를 주기억장치에 전달하고,연산 결과는 출력장치에 전달한다.
피연산자 (Operand)
피연산자에는 주소, 숫자/문자, 논리 데이터 등을 저장할 수 있다.
주소: 기억장치 혹은 레지스터의 주소가 저장된다.
숫자/문자: 숫자는 정수, 고정 소수점 수, 부동 소수점 수 및 각각의 코드로 저장되고 문자는 아스키코드로 저장된다.
논리 데이터: 참 또는 거짓을 표현할 때 사용하며 비트나 플래그로 저장된다.
명령어 사이클
CPU에서는 프로그램을 실행하기 위해 주기억장치에서 명령어를 순차적으로 인출하여 해독하고 실행하는 과정을 반복하는데, CPU가 주기억장치에서 한 번에 하나의 명령어를 인출하여 실행하는데 필요한 일련의 활동을명령어 사이클 (Instruction Cycle)이라고 한다.
명령어 사이클은인출 사이클,실행 사이클, 간접 사이클,인터럽트 사이클로 세분화 시킬 수 있는데, 인출 사이클과 실행 사이클은 항상 수행되지만 / 간접 사이클과 인터럽트 사이클은 주소 지정방식이 필요할 때나 인터럽트 요구가 있을 때만 수행된다.
인출 사이클과특수 목적 레지스터의 동작 과정
이미지 출처 : https://ndb796.tistory.com/7
프로그램 카운터(PC)에 저장된 주소를 메모리 주소 레지스터(MAR)로 전달 한다.
메모리 주소 레지스터(MAR)에 저장된 내용을 토대로 주기억장치의 해당 주소에서 명령어를 인출한다.
인출한 명령어를 메모리 버퍼 레지스터(MBR)에 저장한다.
다음 명령어를 인출하기 위해 프로그램 카운터 (PC)의 값을 증가 시킨다.
메모리 버퍼 레지스터(MBR)에 저장된 내용을 명령어 레지스터(IR)에 전달한다.
위의 과정을 다음과 같이 표현하기도 한다.
T0 : MAR <- PC
T1 : MBR <- M[MAR], PC <- PC + 1
T2 : IR <- MBR
다음은 인출 사이클로부터 명령어를 인출한 이후 명령어를 실행하는 과정인 실행 사이클의 과정이다.
그 중에서도더하기(ADD) 연산으로 과정을 살펴보자.
실행 사이클과특수 목적 레지스터의 동작 과정
이미지 출처 : https://ndb796.tistory.com/7
명령어 레지스터(IR)의 내용을 메모리 주소 레지스터(MAR)로 전달한다.
메모리에 저장된 데이터 값을 메모리 버퍼 레지스터(MBR)에 저장한다.
누산기(AC)에 저장된 값에 ADD연산을 실행한다.
실행 사이클도 인출 사이클과 마찬가지로 다음과 같이 표현 할 수 있다.
ADD addr 명령어 연산
T0 : MAR <- IR(Addr)
T1 : MBR <- M[MAR]
T2 : AC <- AC + MBR
실행 사이클에서는 프로그램 카운터를 증가시키지 않는 이유 인출 사이클과 다르게 실행 사이클에서는 프로그램 카운터(PC)를 증가시키지 않는데, 이미 인출이 진행 되고 명령어 실행만 하면 되는 상황이기 때문에 프로그램 카운터를 증가시킬 필요가 없다. 즉, 이미 인출이 되어 명령어 레지스터(IR)에 메모리 버퍼 레지스터(MBR)의 값이 저장된 상태라는 의미이다.
① 먼저 초기의 파이어볼을 입력받은 후에 fireball라는 큐와 graph의 각 칸에 파이어볼을 삽입합니다.
fireball 큐는 현재 존재하는 파이어볼의 위치를 저장하는 큐이고
graph는 N x N 그래프(맵 전체)를 나타냅니다.
이 때, graph의 각 칸에는 그 칸에 존재하는 모든 파이어볼의 정보(질량, 방향, 속력)를 저장합니다.
② 파이어볼을 큐에서 꺼냅니다.
꺼낸 파이어볼의 칸으로 가서 파이어볼 정보를 꺼낸 후(pop) 이 정보를 토대로 파이어볼을 이동 시킵니다.
(이동은 옮길 칸에 정보(m, s, d)를 넣어줍니다.)
이 때, 아직 파이어볼이 합쳐질지 말지는 모르기 때문에 파이어볼큐에는 파이어볼을 넣지 않습니다.
③ 이동이 끝난 후, 파이어볼이 2개 이상 존재하는 칸은
문제에서 제시한 규칙대로 파이어볼을 하나로 합친 후에 4개로 나눕니다.
④ 나누어졌다면 바뀐 정보를 다시 해당 칸에 넣어주고, 위치는 fireball 큐에 삽입합니다.
⑤ 파이어볼이 1개만 존재하는 칸은 그대로 다시 파이어볼에 삽입합니다.
② ~ ⑤ 과정을 K번 반복한 후 정답을 출력하면 됩니다.
from collections import deque
n, m, k = map(int, input().split())
graph = [[deque() for _ in range(n)] for _ in range(n)]
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]
fireball = deque()
for i in range(m):
r, c, m, s, d = map(int, input().split())
fireball.append([r-1, c-1])
graph[r-1][c-1].append(deque([m, s, d]))
for _ in range(k):
for j in range(len(fireball)):
r, c = fireball.popleft()
m, s, d = graph[r][c].popleft()
nr = (r + s*dx[d]) % n
nc = (c + s*dy[d]) % n
graph[nr][nc].append(deque([m, s, d]))
for i in range(n):
for j in range(n):
if len(graph[i][j]) > 1:
sum_m, sum_s, odd_d, even_d, cnt = 0, 0, 0, 0, 0
while graph[i][j]:
m, s, d = graph[i][j].popleft()
sum_m += m
sum_s += s
cnt += 1
if d % 2 == 0:
even_d += 1
else:
odd_d += 1
sum_m //= 5
if sum_m == 0:
continue
sum_s //= cnt
if even_d == cnt or odd_d == cnt:
dir = [0, 2, 4, 6]
else:
dir = [1, 3, 5, 7]
for d in range(4):
fireball.append([i, j])
graph[i][j].append(deque([sum_m, sum_s, dir[d]]))
elif len(graph[i][j]) == 1:
fireball.append([i, j])
answer = 0
for i in range(n):
for j in range(n):
answer += sum(arr[0] for arr in graph[i][j])
print(answer)
문제의 설명이 굉장히 긴 편이라 위 링크의 문제를 꼼꼼히 읽어보시고 풀이과정을 살펴보시길 추천드립니다.
일반적인 BFS/ DFS 문제보다 신경써서 구현해야 할 부분들이 훨씬 까다로운 문제이므로
과정을 하나하나 잘 살펴보면서 구현하시는 것을 추천드립니다.
풀이 과정
먼저 두 방법으로 풀면서 코드를 두 가지로 작성해보았습니다.
코드①은 구현해야 할 부분들을 그대로 나열식으로 작성한 코드이며 길이가 좀 더 깁니다.
코드②는 코드①을 좀더 깔끔하고, 중복되는 코드들을 줄여 정리한 코드입니다.
두 코드 모두 접근 방식은 같습니다.
먼저 공통되는 부분인 rotate(회전)함수와 gravity(중력)함수부터 설명드리자면,
rotate는 반시계(왼쪽)방향으로 90도 회전을 해야 하기 때문에
(0, 0) 좌표는 => (n-1, 0) 좌표로 이동을 하게 되고
(0, 1) 좌표는 => (n-2, 0) 좌표로 이동을 하게 됩니다.
이런식으로 직접 행렬을 그려서 비교해보면
(x, y) 좌표는 => (n-1-y, x) 좌표로 이동함을 알 수 있습니다.
gravity는 벽(-1)이나 경계를 만날 때 까지 아래 빈칸으로 계속 쭉 떨어지게 됩니다.
그래서 밑의 행부터 시작하여 차례대로 while문을 통해 내려갈 수 있는 곳 까지 내려가게 해줍니다.
이제 핵심이 되는 BFS 코드(find_group함수)입니다.
풀이①은 문제에서 조건1에 해당하는
크기가 가장 큰 블록 그룹을 찾는다.
그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹,
그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을,
그 것도 여러개이면 열이 가장 큰 것을 찾는다.
이 부분을 함수 안에 같이 구현을 하였습니다.
while문을 통해 그룹을 지은 다음, 그룹의 크기가 2보다 작으면 그룹을 만들지 않고 return 합니다.
현재 만든 그룹과 최대 그룹을 비교를 해서
현재 만든 그룹이 더 크면 최대 그룹을 바꿔줍니다.
크기가 같다면, 무지개 블록의 수가 많은 블록을 최대 그룹으로 하고
그것마저 같다면 기준행, 열을 비교하여 선정을 하면 됩니다.
이 방법을 모두 find_group 함수 안에 순서대로 작성하였습니다.
코드①
from collections import deque
n, m = map(int, input().split())
graph = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
for i in range(n):
graph.append(list(map(int, input().split())))
def find_group(a, b):
visited = [[False] * n for _ in range(n)]
groupQ = []
if graph[a][b] == -1 or graph[a][b] == -2:
return
if graph[a][b] > 0:
myColor = graph[a][b]
else:
myColor = 0
cnt = 1
queue = deque()
queue.append((a, b))
visited[a][b] = True
while queue:
x, y = queue.popleft()
groupQ.append((x, y))
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= n or visited[nx][ny]:
continue
if graph[nx][ny] == -1 or graph[nx][ny] == -2:
continue
if graph[nx][ny] > 0:
if myColor == 0:
myColor = graph[nx][ny]
elif myColor != graph[nx][ny]:
continue
cnt += 1
queue.append((nx, ny))
visited[nx][ny] = True
if cnt < 2:
return
global groupCnt, maxQ
if cnt > groupCnt:
groupCnt = cnt
maxQ = groupQ
elif cnt == groupCnt:
thisZeroCnt, maxZeroCnt = 0, 0
for i in range(cnt):
if graph[groupQ[i][0]][groupQ[i][1]] == 0:
thisZeroCnt += 1
for i in range(groupCnt):
if graph[maxQ[i][0]][maxQ[i][1]] == 0:
maxZeroCnt += 1
if thisZeroCnt == maxZeroCnt:
groupQ.sort(key=lambda x: x[1])
groupQ.sort(key=lambda x: x[0])
maxQ.sort(key=lambda x: x[1])
maxQ.sort(key=lambda x: x[0])
gx, gy, mx, my = 0, 0, 0, 0
for i in range(cnt):
if graph[groupQ[i][0]][groupQ[i][1]] != 0:
gx = groupQ[i][0]
gy = groupQ[i][1]
break
for i in range(groupCnt):
if graph[maxQ[i][0]][maxQ[i][1]] != 0:
mx = maxQ[i][0]
my = maxQ[i][1]
break
if gx > mx:
maxQ = groupQ
elif gx == mx:
if gy > my:
maxQ = groupQ
elif thisZeroCnt > maxZeroCnt:
maxQ = groupQ
return
def gravity():
for i in range(n-2, -1, -1):
for j in range(n):
if graph[i][j] != -1:
tmp = i
while tmp + 1 < n and graph[tmp+1][j] == -2:
graph[tmp+1][j] = graph[tmp][j]
graph[tmp][j] = -2
tmp += 1
def rotate():
newGraph = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
newGraph[n - 1 - j][i] = graph[i][j]
return newGraph
answer = 0
while True:
groupCnt = 0
maxQ = []
for i in range(n):
for j in range(n):
if graph[i][j] > 0:
find_group(i, j)
if not maxQ:
break
answer += len(maxQ)**2
for x, y in maxQ:
graph[x][y] = -2
gravity()
graph = rotate()
gravity()
print(answer)
코드 1과 다른 부분은 BFS코드(find_group함수)입니다.
코드②은 find_group함수에서는 일단 그룹을 형성하여 그 그룹의 크기와 0(무지개)크기, 일반블록+무지개블록의 좌표를 담은 리스트를 반환을 해주었고
이 리스트들을 하나의 큐에 넣은 후에
정렬을 통해 최대 큐(조건에 맞는 큐)를 선정하였습니다.
또한, visited를 함수 안이 아닌 바깥에 선언을 함으로써, 중복으로 형성하는 그룹을 없앴고
대신, 0칸(무지개)은 다음턴에 다른 그룹들과도 형성될 수 있으므로
다시 미방문 처리를 해주어야 합니다.
코드②
from collections import deque
n, m = map(int, input().split())
graph = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
for i in range(n):
graph.append(list(map(int, input().split())))
def find_group(a, b, color):
queue = deque()
queue.append([a, b])
block_cnt, zero_cnt = 1, 0
blocks = [[a, b]]
zeros = []
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= n or visited[nx][ny]:
continue
if graph[nx][ny] == color:
visited[nx][ny] = True
queue.append([nx, ny])
block_cnt += 1
blocks.append([nx, ny])
elif graph[nx][ny] == 0:
visited[nx][ny] = True
queue.append([nx, ny])
block_cnt += 1
zeros.append([nx, ny])
zero_cnt += 1
for x, y in zeros:
visited[x][y] = False
return [block_cnt, zero_cnt, blocks + zeros]
def gravity():
for i in range(n-2, -1, -1):
for j in range(n):
if graph[i][j] != -1:
tmp = i
while tmp + 1 < n and graph[tmp+1][j] == -2:
graph[tmp+1][j] = graph[tmp][j]
graph[tmp][j] = -2
tmp += 1
def rotate():
newGraph = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
newGraph[n - 1 - j][i] = graph[i][j]
return newGraph
answer = 0
while True:
visited = [[False]*n for _ in range(n)]
maxQ = []
for i in range(n):
for j in range(n):
if graph[i][j] > 0 and not visited[i][j]:
visited[i][j] = True
block = find_group(i, j, graph[i][j])
if block[0] >= 2:
maxQ.append(block)
print(maxQ)
maxQ.sort(reverse=True)
if not maxQ:
break
answer += maxQ[0][0]**2
for x, y in maxQ[0][2]:
graph[x][y] = -2
gravity()
graph = rotate()
gravity()
print(graph)
print(answer)
문제의 설명이 굉장히 긴 편이라 위 링크의 문제를 꼼꼼히 읽어보시고 풀이과정을 살펴보시길 추천드립니다.
이 문제는, 특별한 알고리즘 없이 문제에서 주어진 사항을 구현하는 문제이지만
구현해야 하는 부분들이 굉장히 까다로운 문제였습니다
풀이 과정
풀이과정이 굉장히 길기 때문에, 잘 모르시는 부분을 중점으로 보시는 것을 추천드립니다.
① 먼저, 가운데 칸(n//2, n//2)은 상어가 있는 곳이며 여기를 시작으로 하여 토네이도처럼 돌아
각 칸에 인덱스를 붙여줘야 한다.(1, 2, 3... n*n)
이 부분은 indexing함수에서 구현하였다.
② 그리고 상어가 마법을 시전하는데, 이 부분은 magic함수에 구현하였다.
위 아래 왼쪽 오른쪽 4방향중에 1방향과 거리가 주어지며
마법 후 해당 칸의 숫자는 사라진다.
해당칸을 0으로 표현함으로써 사라졌음을 표시하였다.
③ 사라진 후에는 빈 칸만큼 뒷 칸들이 당겨야 하기 때문에 이부분은 fill_blank 함수에 구현하였다.
1번 칸부터 순서대로 돌면서 0인 칸(즉, 빈칸)을 발견하면 그 칸을 blankIdx라는 큐에 넣어준 상태로
빈 칸을 만나지 않았을 때, 큐에서 빈칸의 인덱스를 꺼내어
그 칸에 현재 칸의 수를 넣어주고, 현재 칸은 0으로(빈 상태) 만들어줌으로써 당겨주었다.
모두 당겨질 때 까지 반복한다.
④ 이제, 연속된 숫자가 4칸 이상 존재한다면 그 칸들을 폭발시킨다.
이 부분은 bomb 함수에 구현하였다.
처음에는 저장할 숫자가 없으므로 임시로 -1을 지정하였고
칸을 돌면서 전 칸과 같은 숫자가 발생한다면 카운트를 늘려나간다.
그러다가 저장하고 있는 숫자와 다른 수를 만났을 때, 저장하고 있는 수의 카운트가 4 이상이라면 폭발해야하므로
그 칸들을 모두 0으로 바꿔준다. 그리고 점수계산을 해야 하므로 점수도 함께 저장한다.
⑤ 폭발 후에는 그룹을 지어야 한다.
이 부분은 grouping 함수에 구현하였다.
from collections import deque
n, m = map(int, input().split())
graph = []
cmd = []
score = [0]*3
def indexing():
x, y = n // 2, n // 2
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
depth = 0
while True:
for i in range(4):
if i % 2 == 0:
depth += 1
for j in range(depth):
x += dx[i]
y += dy[i]
graphIdx.append((x, y))
if x == 0 and y == 0:
return
def magic(dir, dist):
x, y = n // 2, n // 2
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(dist):
x += dx[dir]
y += dy[dir]
if x < 0 or x >= n or y < 0 or y >= n:
break
graph[x][y] = 0
fill_blank()
while bomb():
fill_blank()
grouping()
def fill_blank():
blankIdx = deque()
for x, y in graphIdx:
if graph[x][y] == 0:
blankIdx.append((x, y))
elif graph[x][y] > 0 and blankIdx:
nx, ny = blankIdx.popleft()
graph[nx][ny] = graph[x][y]
graph[x][y] = 0
blankIdx.append((x, y))
def bomb():
visited = deque()
cnt = 0
num = -1
flag = False
for x, y in graphIdx:
if num == graph[x][y]:
visited.append((x, y))
cnt += 1
else:
if cnt >= 4:
score[num-1] += cnt
flag = True
while visited:
nx, ny = visited.popleft()
if cnt >= 4:
graph[nx][ny] = 0
num = graph[x][y]
cnt = 1
visited.append((x, y))
return flag
def grouping():
cnt = 1
tmpx, tmpy = graphIdx[0]
num = graph[tmpx][tmpy]
nums = []
for i in range(1, len(graphIdx)):
x, y = graphIdx[i][0], graphIdx[i][1]
if num == graph[x][y]:
cnt += 1
else:
nums.append(cnt)
nums.append(num)
num = graph[x][y]
cnt = 1
idx = 0
for x, y in graphIdx:
if not nums:
break
graph[x][y] = nums[idx]
idx += 1
if idx == len(nums):
break
for i in range(n):
graph.append(list(map(int, input().split())))
for i in range(m):
d, s = map(int, input().split())
cmd.append((d, s))
graphIdx = deque()
indexing()
for a, b in cmd:
magic(a-1, b)
answer = 0
for i in range(3):
answer += (i+1) * score[i]
print(answer)
큰 제약사항이나 알고리즘이 따로 사용되지는 않으므로 순서에 맞게 그대로 구현만 잘 해주면 된다.
풀이 과정
문제에서 특별히 신경써주어야 하는 부분은, 조건5 부분이다.
먼저, 구름이 di 방향으로 si칸 이동한 후에 비를 뿌리고 구름은 사라진다.
이 때, 구름이 사라진 칸은 물복사 버그 후에 구름이 생길 수 없기 때문에 1로 표시해주어
해당 턴에 구름이 생길 수 없도록 해주었다.
그리고 그 칸에 영원히 구름이 생길 수 없는 것이 아니라,
해당 턴에만 생길 수 없기 때문에
raining 함수의 마지막 부분에 1로 표시해둔 칸을 다시 0으로 표시하여 구름이 생길 수 있도록 해주었다.
코드의 cloud는 현재 턴에서 처음의 구름 위치를 담은 큐이고
queue는 이 구름들을 이동시킨 후의 구름 위치이다.
from collections import deque
n, m = map(int, input().split())
board = []
rain = [[0] * n for _ in range(n)]
dx = [0, -1, -1, -1, 0, 1, 1, 1]
dy = [-1, -1, 0, 1, 1, 1, 0, -1]
for i in range(n):
board.append(list(map(int, input().split())))
cloud = deque([(n - 1, 0), (n - 1, 1), (n - 2, 0), (n - 2, 1)])
def raining(dir, dist):
queue = deque()
while cloud:
a, b = cloud.popleft()
nx = (a + dx[dir] * dist) % n
ny = (b + dy[dir] * dist) % n
board[nx][ny] += 1
rain[nx][ny] = 1 # 사라진 칸은 1 표시
queue.append((nx, ny))
while queue:
a, b = queue.popleft()
for i in range(1, 8, 2):
nx = a + dx[i]
ny = b + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if board[nx][ny] > 0:
board[a][b] += 1
for i in range(n):
for j in range(n):
if rain[i][j] == 1:
rain[i][j] = 0
continue
if board[i][j] >= 2:
cloud.append((i, j))
board[i][j] -= 2
for i in range(m):
d, s = map(int, input().split())
raining(d - 1, s)
answer = 0
for i in range(n):
answer += sum(board[i])
print(answer)
