열의 수 M에 따라서 3명을 배치하는 모든 경우의 수를 구해야 하므로 조합을 이용해 풀어야 하는 문제입니다.
이 문제는 총 4번의 과정을 통하여 문제를 풀어보겠습니다.
입력값 받기
궁수 위치 정하기
궁수가 처치할 적 선택 후 적 처치
적들 이동하기, 처치한 적의 수 추가하기
1. 입력값 받기
이번엔 조합을 사용하므로 입력값을 넣는 변수를 만들어주고, 조합을 불러오면 됩니다.
from itertools import combinations as cbn, m, d =map(int,input().split())MAP =list(list(map(int,input().split())) for _ inrange(n))
2. 궁수 위치 정하기
먼저 궁수는 n행에 전부 위치할 것이고, m칸 중에서 3개를 선택하면 됩니다.
그래서 0 ~ m-1까지의 정수를 저장한 리스트(Castle)를 만들어주고, 조합을 이용해 3개를 선택하면 됩니다.
from itertools import combinations as cbn, m, d =map(int,input().split())MAP =list(list(map(int,input().split())) for _ inrange(n))Castle = [i for i inrange(m)]Archer =cb(Castle, 3)
이제 궁수들의 위치를 정하였으니 for문을 이용하여 돌려주면 됩니다. 그 전에 궁수 위치에 따라 죽일 수 있는 적의 최대 수를 출력해야 하므로 ans = 0을 추가합시다.
그리고 맵을 수정해야 하므로 deepcopy 모듈을 불러와서 깊은 복사를 해주면 됩니다.
from itertools import combinations as cbfrom copy import deepcopyn, m, d =map(int,input().split())MAP =list(list(map(int,input().split())) for _ inrange(n))Castle = [i for i inrange(m)]Archer =cb(Castle, 3)ans =0for S in Archer: arr =deepcopy(MAP) blah blah
3. 궁수가 처치할 적 선택 후 적 처치
이제 적군이 궁수가 있는 행으로 오기 전에 적군을 처치해야 합니다.
적군을 죽이는 조건은 거리가 d 이하에 있는 적중에서 가장 가까운 적, 가장 가까운 적이 여럿이면 가장 왼쪽에 있는 적이고, 같은 적이 여러 궁수에게 공격당할 수 있다고 합니다.
적의 위치를 찾는 것은 2중 for문으로 하면 해결될 것이고, 2중 for문을 돌리면서 적을 만났을 경우 궁수와의 거리를 확인해보고, 궁수가 죽일 적을 업데이트하면 됩니다.
from itertools import combinations as cbfrom copy import deepcopyn, m, d =map(int,input().split())MAP =list(list(map(int,input().split())) for _ inrange(n))Castle = [i for i inrange(m)]Archer =cb(Castle, 3)ans =0for S, b, c in Archer: arr =deepcopy(MAP) dist = [d+1]*3 enemy = [(-1,-1)] *3
이렇게 궁수와의 거리는 dist 배열이고, enemy는 궁수가 죽일 적의 위치를 나타내는 배열입니다.
이제 2중 for문을 사용하여 적을 찾고, 업데이트면 됩니다. 여기서 가장 왼쪽에 있는 적을 선택해야 하므로 아래 코드처럼 행과 열의 탐색 순서를 바꾸어줘야 합니다.
from itertools import combinations as cbfrom copy import deepcopyn, m, d =map(int,input().split())MAP =list(list(map(int,input().split())) for _ inrange(n))Castle = [i for i inrange(m)]Archer =cb(Castle, 3)ans =0for S in Archer: arr =deepcopy(MAP) dist = [d+1]*3 enemy = [(-1,-1)] *3for j inrange(m):for i inrange(n):if arr[i][j] ==1:for k inrange(3): ax, ay = n, S[k] ex, ey = i, jif dist[k]>abs(ax-ex)+abs(ay-ey): dist[k]=abs(ax-ex)+abs(ay-ey) enemy[k]= (ex, ey)
각 궁수가 처치할 적들을 고를 수 있으면 적의 위치를 설정해주었고, 거리가 멀어서 설정하지 못한 경우에는 enemy[i] = (-1, -1)로 설정되어 있을 겁니다. 그래서 x != -1 and y != -1일 때, arr[x][y] = 0을 해줍니다.
from itertools import combinations as cbfrom copy import deepcopyn, m, d =map(int,input().split())MAP =list(list(map(int,input().split())) for _ inrange(n))Castle = [i for i inrange(m)]Archer =cb(Castle, 3)ans =0for S in Archer: arr =deepcopy(MAP) dist = [d+1]*3 enemy = [(-1,-1)] *3for j inrange(m):for i inrange(n):if arr[i][j] ==1:for k inrange(3): ax, ay = n, S[k] ex, ey = i, jif dist[k]>abs(ax-ex)+abs(ay-ey): dist[k]=abs(ax-ex)+abs(ay-ey) enemy[k]= (ex, ey)for x, y in enemy:if x !=-1and y !=-1: arr[x][y] =0
4. 적들 이동하기, 처치한 적의 수 추가하기
이제 적들을 한 칸씩 내립니다. 이것은 for문을 이용해서 arr[i][j] = arr[i-1][j]로 업데이트해주면 쉽게 만들 수 있습니다.
from itertools import combinations as cbfrom copy import deepcopyn, m, d =map(int,input().split())MAP =list(list(map(int,input().split())) for _ inrange(n))Castle = [i for i inrange(m)]Archer =cb(Castle, 3)ans =0for S in Archer: arr =deepcopy(MAP) dist = [d+1]*3 enemy = [(-1,-1)] *3for j inrange(m):for i inrange(n):if arr[i][j] ==1:for k inrange(3): ax, ay = n, S[k] ex, ey = i, jif dist[k]>abs(ax-ex)+abs(ay-ey): dist[k]=abs(ax-ex)+abs(ay-ey) enemy[k]= (ex, ey)for x, y in enemy:if x !=-1and y !=-1: arr[x][y] =0for i inrange(n -1, -1, -1):for j inrange(m):if i ==0: arr[i][j] =0continueelse: arr[i][j] = arr[i -1][j]
처음부터 적이 없을 수도 있는 경우가 존재할 수 있으므로 12줄 다음 줄에 2중 for문으로 적이 있는지 확인해보면 됩니다.
from itertools import combinations as cbfrom copy import deepcopyn, m, d =map(int,input().split())MAP=list(list(map(int,input().split())) for _ inrange(n))Castle = [i for i inrange(m)]Archer =cb(Castle, 3)ans =0for S in Archer: arr =deepcopy(MAP) flag =Falsefor i inrange(n):for j inrange(m):if arr[i][j] ==1: flag =Trueifnot flag:break dist = [d+1]*3 enemy = [(-1,-1)] *3for j inrange(m):for i inrange(n):if arr[i][j] ==1:for k inrange(3): ax, ay = n, S[k] ex, ey = i, jif dist[k]>abs(ax-ex)+abs(ay-ey): dist[k]=abs(ax-ex)+abs(ay-ey) enemy[k]= (ex, ey)for x, y in enemy:if x !=-1and y !=-1: arr[x][y] =0for i inrange(n -1, -1, -1):for j inrange(m):if i ==0: arr[i][j] =0continueelse: arr[i][j] = arr[i -1][j]
그리고 문제 본문에 적들이 모두 제외되면 해당 게임은 끝난다고 하므로 적이 전부 사라질 때까지 반복하면 됩니다. 그래서 11줄을 제외한 for문에 있는 내용 전부를 while문 무한 루프를 씌워줘야 합니다.
from itertools import combinations as cbfrom copy import deepcopyn, m, d =map(int, input().split())MAP =list(list(map(int, input().split())) for _ inrange(n))Castle = [i for i inrange(m)]Archer =cb(Castle, 3)ans =0for S in Archer: arr =deepcopy(MAP)while1: flag =Falsefor i inrange(n):for j inrange(m):if arr[i][j] ==1: flag =Trueifnot flag:break dist = [d+1] *3 enemy = [(-1,-1)] *3for j inrange(m):for i inrange(n):if arr[i][j] ==1:for k inrange(3): ax, ay = n, S[k] ex, ey = i, jif dist[k]>abs(ax - ex)+abs(ay - ey): dist[k]=abs(ax - ex)+abs(ay - ey) enemy[k]= (ex, ey)for x, y in enemy:if x !=-1and y !=-1: arr[x][y] =0for i inrange(n -1, -1, -1):for j inrange(m):if i ==0: arr[i][j] =0continueelse: arr[i][j] = arr[i -1][j]
적을 제거할 때마다 적을 죽인 수를 구해야 하므로 ans 값을 업데이트 해줄 kill = 0 변수를 12줄 다음 줄에 추가해주고, 31~33줄에 있는 for문에 arr[x][y] = 1이면 kill += 1, arr[x][y] = 0을 해주면 됩니다. 그리고 for문 마지막 줄에 ans = max(ans, kill)을 해주어서 ans의 값을 업데이트하면 됩니다.
from itertools import combinations as cbfrom copy import deepcopyn, m, d =map(int, input().split())MAP =list(list(map(int, input().split())) for _ inrange(n))Castle = [i for i inrange(m)]Archer =cb(Castle, 3)ans =0for S in Archer: arr =deepcopy(MAP) kill =0while1: flag =Falsefor i inrange(n):for j inrange(m):if arr[i][j] ==1: flag =Trueifnot flag:break dist = [d+1]*3 enemy = [(-1,-1)] *3for j inrange(m):for i inrange(n):if arr[i][j] ==1:for k inrange(3): ax, ay = n, S[k] ex, ey = i, jif dist[k]>abs(ax - ex)+abs(ay - ey): dist[k]=abs(ax - ex)+abs(ay - ey) enemy[k]= (ex, ey)for x, y in enemy:if x !=-1and y !=-1:if arr[x][y] ==1: kill +=1 arr[x][y] =0for i inrange(n -1, -1, -1):for j inrange(m):if i ==0: arr[i][j] =0continueelse: arr[i][j] = arr[i -1][j] ans =max(ans, kill)print(ans)