[파이썬] 백준 23290 : 마법사 상어와 복제 (골드1)

[파이썬] 백준 23290 : 마법사 상어와 복제 (골드1)

 

23290번: 마법사 상어와 복제

---

문제

---

풀이

0. 방향성 생각

같은 격자에 같은 방향을 가진 물고기들이 매우 많아질 수 있다. 테스트 케이스를 보면 답이 60만이 넘어가기도 한다.

예를들어 리스트로 사용하면 특정 좌표에만 [1,1,2,3,4,4,4,4,4,4,5,7,7,.........,8] 이런식으로 매우 길어질 수 있다.

 

이를 간단하게 처리하기 위해 딕셔너리를 사용. 딕셔너리[좌표][물고기 방향] = 마리수

이런식으로 정의한다. 1~8까지 정의하고 물고기 방향이 0인 경우에는 그 좌표의 총 마리수를 채워준다.

 

1. 원본 좌표정보 복사 -> 카피본 생성

2. 카피본에서 물고기 이동

3. 카피본에서 상어 이동 : 이동경로 모두 찾기

4. 최적의 경로 선택

5. 최적 경로를 바탕으로 격자 카피본 업데이트

6. 복제 진행 : 카피본 + 원본 = 새로운 원본 생성

 

1. 좌표 정보, 냄새 정보, 방향 정보 정의하기

fishes = {(j,i): {k: 0 for k in range(9)} for i in range(4) for j in range(4)}
smells = {(j,i): 0 for i in range(4) for j in range(4)}

fish_step = {1:(-1,0), 2:(-1,-1), 3:(0,-1),
              4:(1,-1), 5:(1,0), 6:(1,1),
              7:(0,1), 8:(-1,1), 0:(-1,1)}
shark_step = {1:(0,-1), 2:(-1,0), 3:(0,1), 4:(1,0)}

fishes[좌표][방향] = 물고기 수 (방향이 0인 경우에는 총 물고기 수) 

fishes[좌표][방향] = 냄새 0~2

방향정보 정의할 때는 리스트에서 상하좌우 정보 착각하지 않도록 주의하기

2. 입력

count,cmd = map(int,input().split())
for _ in range(count):
    y,x,d = map(int,input().split())
    fishes[(x-1,y-1)][d] += 1
    fishes[(x-1,y-1)][0] += 1
y,x = map(int,input().split())
sy,sx = y-1,x-1

y,x순으로 들어온다. 이거 놓쳐서 20분은 썼다.

입력이 들어오면 fishes[좌표][방향] += 1해주고, 입력이 들어왔으므로 총 마리수 fishes[좌표][0] += 1 해준다.

상어 좌표는 sy,sx순으로 받는다.

3. 원본 좌표정보 복사

def copy_fish(origin):
    copy = {(j,i): {k: 0 for k in range(9)} for i in range(4) for j in range(4)}
    for loc in origin.keys():
        for i in range(9):
            copy[loc][i] = origin[loc][i]
    return copy

deepcopy를 사용하거나 리스트/딕셔너리 컴프리헨션으로 복사를 진행한다.

copy는 이게 꼬인다고? 하는 경우가 생겨서 이렇게 복사를 반복해서 하는 경우에는 그냥 새로 정의한다.

4. 물고기 이동

def fish_move(before_move):
    
    global sx,sy,fish_step
    # 딕셔너리 컴프리헨션으로 초기화
    after_move = {(j,i): {k: 0 for k in range(9)} for i in range(4) for j in range(4)}

    for loc in before_move.keys():
        if before_move[loc][0]:
            fx,fy = loc
            for head in range(1,9):
                if before_move[loc][head]:
                    cant_move = True
                    for i in range(8,0,-1):
                        nhead = (head+i)%8
                        nhead = 8 if nhead == 0 else nhead
                        dx,dy = fish_step[nhead]
                        nfx = fx + dx
                        nfy = fy + dy
                        if 0<=nfx<4 and 0<=nfy<4 and (nfx,nfy)!=(sx,sy) and smells[(nfx,nfy)] == 0:
                            after_move[(nfx,nfy)][nhead] += before_move[loc][head]
                            after_move[(nfx,nfy)][0] += before_move[loc][head]
                            cant_move = False
                            break
                    if cant_move:
                        after_move[loc][head] += before_move[loc][head]
                        after_move[loc][0] += before_move[loc][head]
    return after_move

 

    global sx,sy,fish_step
    # 딕셔너리 컴프리헨션으로 초기화
    after_move = {(j,i): {k: 0 for k in range(9)} for i in range(4) for j in range(4)}

앞에서 정의한 copy본으로 얻은 딕셔너리 before_move를 함수에 넣는다.

after_move를 딕셔너리 컴프리헨션으로 초기화

 

    for loc in before_move.keys():
        if before_move[loc][0]:
            fx,fy = loc

before_move[좌표][0] 이므로 총 마리수이다. 즉, 물고기가 존재하는 경우 fx,fy를 현재 좌표로 할당한다.

 

            for head in range(1,9):
                if before_move[loc][head]:
                    cant_move = True
                    for i in range(8,0,-1):
                        nhead = (head+i)%8
                        nhead = 8 if nhead == 0 else nhead
                        dx,dy = fish_step[nhead]
                        nfx = fx + dx
                        nfy = fy + dy

1부터 8까지 모든 방향에 대해서 탐색한다.

before_move[좌표][방향]에 물고기가 존재할 경우 탐색 진행.

일단 cant_move를 이후에 이동 불가능한 경우에 사용하는 flag 정의한다.

 

총 8가지 방향에 대해서 반시계 방향으로 돌린다.

여기서 모듈러 연산을 사용해주고 8인 경우에는 0이 되버리면 총 마리수에 대해서 접근하므로,

다음 방향이 0인 경우에는 8로 할당한다.

다음 좌표 nfx,nfy를 구한다.

                        if 0<=nfx<4 and 0<=nfy<4 and (nfx,nfy)!=(sx,sy) and smells[(nfx,nfy)] == 0:
                            after_move[(nfx,nfy)][nhead] += before_move[loc][head]
                            after_move[(nfx,nfy)][0] += before_move[loc][head]
                            cant_move = False
                            break
                    if cant_move:
                        after_move[loc][head] += before_move[loc][head]
                        after_move[loc][0] += before_move[loc][head]
    return after_move

다음 좌표가 격자 내에 있고, 상어 위치가 아니며, 냄새가 남아있지 않은 경우에 이동 가능하다.

avter_move[다음좌표][다음방향] += before_move[이전좌표][이전방향]으로 마리수를 업데이트한다.

이동할 수 있으면 나머지 경우에는 탐색하지 않아도 되므로 break

이동 불가능하면 비슷한 방식으로 업데이트

 

5. 상어 이동동선 탐색

def shark_move(x0,y0):
    
    global sx,sy,shark_step
    
    path = []
    for a in range(4):
        dx0,dy0 = shark_step[a+1]
        x1 = x0 + dx0
        y1 = y0 + dy0
        if 0<=x1<4 and 0<=y1<4:
            for b in range(4):
                dx1,dy1 = shark_step[b+1]
                x2 = x1 + dx1
                y2 = y1 + dy1
                if 0<=x2<4 and 0<=y2<4:
                    for c in range(4):
                        dx2,dy2 = shark_step[c+1]
                        x3 = x2 + dx2
                        y3 = y2 + dy2
                        if 0<=x3<4 and 0<=y3<4:
                            path.append([int(str(a+1)+str(b+1)+str(c+1)),
                                         [(x1,y1),(x2,y2),(x3,y3)]])
    return path

그냥 무식하게 3중 for문으로 작성했다. 시간재고 푸니까 재귀같은거는 실전에서 쓰기 좀 어렵다.

path에 이동 가능한 모든 경로를 [123,[좌표1,좌표2,좌표3]] 형식으로 넣었다.

 

6. 최적 경로 찾기

def find_best(after_move,path):

    score = []
    for key,locs in path:
        count = 0
        visit,eat = set(),set()
        for loc in locs:
            if loc not in visit:
                visit.add(loc)
                if after_move[loc][0]:
                    count += after_move[loc][0]
                    eat.add(loc)
        score.append([count,key,loc,eat])
    score.sort(key=lambda x:(x[0],-x[1]))
    return score[-1]

경로에 대해서 [좌표1 좌표2 좌표3] 리스트를 locs로 받는다.

locs를 반복해서 3칸을 탐색한다. 이 때 처음 방문할 때에만 물고기 카운트를 한다.

좌 우 좌 같은경우에 좌에서 물고기를 두 번 셀 수 있으므로, 방문처리를 해주어서 첫 방문만 카운트한다.

그 후 먹은 물고기 수, 사전순으로 정렬을 해준다. 맨 뒤에는 가장 많이먹은 경우 + 사전 순 가장 앞선 경우이다.

 

7. 냄새, 상어 위치, 격자 정보 업데이트

def update(score,origin,copy):
    
    global sx,sy,smells
    sx,sy = score[2]
    
    for loc in origin.keys():
        if smells[loc]:
            smells[loc] -= 1

    if score[-1]:
        for ex,ey in score[-1]:
            smells[(ex,ey)] = 2
            origin[(ex,ey)] = {k: 0 for k in range(9)}

    info_update = {(j,i): {k: 0 for k in range(9)} for i in range(4) for j in range(4)}
    for loc in origin.keys():
        for i in range(9):
            info_update[loc][i] = origin[loc][i] + copy[loc][i]
        
    return info_update

smells에서 먼저 냄새가 남아있으면 -1씩 해준다.

score의 맨 뒤에는 먹은 물고기 좌표가 들어있다.

이 좌표가 있는 경우에  smell에 접근해서 냄새를 2로 업데이트하고 원본 격자에 물고기 수를 0으로 초기화한다.

 

이후 info_update를 정의해주고 원본과 이동이 끝난 복사본을 합쳐준다.

 

8. 출력

for i in range(cmd):
    before = copy_fish(fishes)
    after = fish_move(before)
    paths = shark_move(sx,sy)
    best = find_best(after,paths)
    fishes = update(best,after,before)

answer = 0
for loc in fishes.keys():
    answer += fishes[loc][0]
print(answer)

cmd번 돌려주고, 마지막에는 물고기 수만 카운트해서 출력!

---

전체코드

1. 딕셔너리 풀이

import sys
input = lambda : sys.stdin.readline().rstrip()

fishes = {(j,i): {k: 0 for k in range(9)} for i in range(4) for j in range(4)}
smells = {(j,i): 0 for i in range(4) for j in range(4)}

fish_step = {1:(-1,0), 2:(-1,-1), 3:(0,-1),
              4:(1,-1), 5:(1,0), 6:(1,1),
              7:(0,1), 8:(-1,1), 0:(-1,1)}
shark_step = {1:(0,-1), 2:(-1,0), 3:(0,1), 4:(1,0)}

count,cmd = map(int,input().split())
for _ in range(count):
    y,x,d = map(int,input().split())
    fishes[(x-1,y-1)][d] += 1
    fishes[(x-1,y-1)][0] += 1
y,x = map(int,input().split())
sy,sx = y-1,x-1

def copy_fish(origin):
    copy = {(j,i): {k: 0 for k in range(9)} for i in range(4) for j in range(4)}
    for loc in origin.keys():
        for i in range(9):
            copy[loc][i] = origin[loc][i]
    return copy


def fish_move(before_move):
    
    global sx,sy,fish_step
    after_move = {(j,i): {k: 0 for k in range(9)} for i in range(4) for j in range(4)}

    for loc in before_move.keys():
        if before_move[loc][0]:
            fx,fy = loc
            for head in range(1,9):
                if before_move[loc][head]:
                    cant_move = True
                    for i in range(8,0,-1):
                        nhead = (head+i)%8
                        nhead = 8 if nhead == 0 else nhead
                        dx,dy = fish_step[nhead]
                        nfx = fx + dx
                        nfy = fy + dy
                        if 0<=nfx<4 and 0<=nfy<4 and (nfx,nfy)!=(sx,sy) and smells[(nfx,nfy)] == 0:
                            after_move[(nfx,nfy)][nhead] += before_move[loc][head]
                            after_move[(nfx,nfy)][0] += before_move[loc][head]
                            cant_move = False
                            break
                    if cant_move:
                        after_move[loc][head] += before_move[loc][head]
                        after_move[loc][0] += before_move[loc][head]
    return after_move


def shark_move(x0,y0):
    
    global sx,sy,shark_step
    
    path = []
    for a in range(4):
        dx0,dy0 = shark_step[a+1]
        x1 = x0 + dx0
        y1 = y0 + dy0
        if 0<=x1<4 and 0<=y1<4:
            for b in range(4):
                dx1,dy1 = shark_step[b+1]
                x2 = x1 + dx1
                y2 = y1 + dy1
                if 0<=x2<4 and 0<=y2<4:
                    for c in range(4):
                        dx2,dy2 = shark_step[c+1]
                        x3 = x2 + dx2
                        y3 = y2 + dy2
                        if 0<=x3<4 and 0<=y3<4:
                            path.append([int(str(a+1)+str(b+1)+str(c+1)),
                                         [(x1,y1),(x2,y2),(x3,y3)]])
    return path


def find_best(after_move,path):

    score = []
    for key,locs in path:
        count = 0
        visit,eat = set(),set()
        for loc in locs:
            if loc not in visit:
                visit.add(loc)
                if after_move[loc][0]:
                    count += after_move[loc][0]
                    eat.add(loc)
        score.append([count,key,loc,eat])
    score.sort(key=lambda x:(x[0],-x[1]))
    return score[-1]


def update(score,origin,copy):
    
    global sx,sy,smells
    sx,sy = score[2]
    
    for loc in origin.keys():
        if smells[loc]:
            smells[loc] -= 1

    if score[-1]:
        for ex,ey in score[-1]:
            smells[(ex,ey)] = 2
            origin[(ex,ey)] = {k: 0 for k in range(9)}

    info_update = {(j,i): {k: 0 for k in range(9)} for i in range(4) for j in range(4)}
    for loc in origin.keys():
        for i in range(9):
            info_update[loc][i] = origin[loc][i] + copy[loc][i]
        
    return info_update

for i in range(cmd):
    before = copy_fish(fishes)
    after = fish_move(before)
    paths = shark_move(sx,sy)
    best = find_best(after,paths)
    fishes = update(best,after,before)

answer = 0
for loc in fishes.keys():
    answer += fishes[loc][0]
print(answer)

 

2. 리스트 풀이

import sys
input = lambda : sys.stdin.readline().rstrip()

fish_infos = {(j,i): [] for i in range(4) for j in range(4)}
smell_infos = {(j,i): 0 for i in range(4) for j in range(4)}

fish_moves = {1:(-1,0), 2:(-1,-1), 3:(0,-1),
              4:(1,-1), 5:(1,0), 6:(1,1),
              7:(0,1), 8:(-1,1), 0:(-1,1)}
shark_moves = {1:(0,-1), 2:(-1,0), 3:(0,1), 4:(1,0)}

count,cmd = map(int,input().split())
for _ in range(count):
    y,x,d = map(int,input().split())
    fish_infos[(x-1,y-1)].append(d)
y,x = map(int,input().split())
sy,sx = y-1,x-1


def copy_info(origin):
    copy = {}
    for i in range(4):
        for j in range(4):
            copy[(j,i)] = origin[(j,i)][:]
    return copy


def fish_move(before_move):
    global sx,sy
    
    after_move = {(j,i): [] for i in range(4) for j in range(4)}
    for loc in before_move.keys():
        if before_move[loc]:
            fx,fy = loc
            for head in before_move[loc]:
                cant_move = True
                for i in range(8,-1,-1):
                    nhead = (head+i)%8
                    dx,dy = fish_moves[nhead]
                    nfx = fx + dx
                    nfy = fy + dy
                    if 0<=nfx<4 and 0<=nfy<4 and (nfx,nfy)!=(sx,sy) and smell_infos[(nfx,nfy)] == 0:
                        after_move[(nfx,nfy)].append(nhead)
                        cant_move = False
                        break
                if cant_move :
                    after_move[loc].append(head)
    return after_move


def shark_move(x0,y0):
    global sx,sy
    
    path = []
    for a in range(4):
        dx0,dy0 = shark_moves[a+1]
        x1 = x0 + dx0
        y1 = y0 + dy0
        if 0<=x1<4 and 0<=y1<4:
            for b in range(4):
                dx1,dy1 = shark_moves[b+1]
                x2 = x1 + dx1
                y2 = y1 + dy1
                if 0<=x2<4 and 0<=y2<4:
                    for c in range(4):
                        dx2,dy2 = shark_moves[c+1]
                        x3 = x2 + dx2
                        y3 = y2 + dy2
                        if 0<=x3<4 and 0<=y3<4:
                            path.append([int(str(a+1)+str(b+1)+str(c+1)),
                                         [(x1,y1),(x2,y2),(x3,y3)]])
    return path

def best_way(after_move,path):

    score = []
    for key,locs in path:
        count = 0
        visit = set()
        eat = []
        for loc in locs:
            if loc not in visit:
                visit.add(loc)
                if len(after_move[loc]):
                    count += len(after_move[loc])
                    eat.append(loc)
        score.append([count,key,loc,eat])
    score.sort(key=lambda x:(x[0],-x[1]))
    return score[-1]


def update(score,origin,copy):
    
    global sx,sy,smell_infos
    sx,sy = score[2]
    
    for loc in origin.keys():
        if 1 <= smell_infos[loc] <= 2 :
            smell_infos[loc] -= 1

    if score[-1]:
        for ex,ey in score[-1]:
            smell_infos[(ex,ey)] = 2
            origin[(ex,ey)] = []
        
    info_update = {}
    for loc in origin.keys():
        info_update[loc] = origin[loc] + copy[loc]
    return info_update


for _ in range(cmd):
    fish_copys = copy_info(fish_infos)
    after_moves = fish_move(fish_copys)
    paths = shark_move(sx,sy)
    way_info = best_way(after_moves,paths)
    fish_infos = update(way_info,after_moves,fish_copys)
    
answer = 0
for loc in fish_infos.keys():
    answer += len(fish_infos[loc])
print(answer)

처음에 제출했던 풀이.

 

코멘트

소요시간 140분. 어렵다!!!!

엣지케이스가 문제에 주어져서 구현 끝내고 나면 틀릴 요소가 없었음.

구현 끝내고나서 테케 60만 나오는거 돌리니까 2초정도 걸려서 시간걱정 했는데 실전이었으면 그냥 제출..

문제 풀이 전에 엣지케이스, 자료구조 등 효율적인 방법 정하기

 

input = lambda : sys.stdin.readline().rstrip()에서 lambda 빼먹어서 디버깅 한참했음..