[이것이 코딩테스트다] 10일차 - 백준 경쟁적 전염

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다.

Chapter 5 DFS/BFS

오늘 풀이한 문제

[백준 18405] 경쟁적 전염

접근 방법 (오답)

1. 한 리스트 안에 바이러스별로 위치를 저장하고 각 위치를 큐의 시작점으로 사용 

이런식으로 저장

2. virus 리스트를 돌면서 좌표와 index를 하나씩 받아옴

3. 좌표에서 K번씩 퍼트림 (cnt 변수를 사용)

이렇게 했을때 로직은 맞는것 같은데 자꾸 오답이라고 나왔다,, 

 

 👇 문제의 코드,,,

n, k = 3, 3
s, x, y = 2, 3, 2

space = [[1, 0, 2],
        [0, 0, 0],
        [3, 0, 0]]

virus = [[]*v for v in range (k+1)]

## virus위치 리스트 만들기 (index = virus num)
for i in range (n):
    for j in range (n):
        if space[i][j] != 0:
            virus[space[i][j]].append((i,j))

from collections import deque

q = deque()

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for index,vi in enumerate (virus):
    for vx, vy in vi: 
        q.append((vx, vy)) ## virus
        cnt = 0
        while q:
            if cnt == s:
                break
            xx, yy = q.popleft()
            for i in range(4):
                nx = xx+dx[i]
                ny = yy+dy[i]
                if 0 <= nx < n and 0 <= ny < n:
                    if space[nx][ny] == 0:
                        space[nx][ny] = index
                        q.append((nx,ny))
            cnt +=1
            
space[x-1][y-1]

 

아직도 문제가 무엇인지 모르겠으나 책의 해답을 보고 소스코드를 약간 수정하니까 정답이 나왔다

 

👇 수정본

spacen, k = 3, 3
s, x, y = 2, 3, 2

space = [[1, 0, 2],
        [0, 0, 0],
        [3, 0, 0]]

virus = [[]*v for v in range (k+1)]

## virus위치 리스트 만들기 (index = virus num)
for i in range (n):
    for j in range (n):
        if space[i][j] != 0:
            virus[space[i][j]].append((i,j))

from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

q = deque()
for index,vi in enumerate (virus):
    for vx, vy in vi: 
        q.append((index, vx, vy, 0)) ## virus, virus_x, virus_y, start time
        while q:
            v_i,xx, yy, v_s = q.popleft()
            if v_s == s:
                break
            for i in range(4):
                nx = xx+dx[i]
                ny = yy+dy[i]
                if 0 <= nx < n and 0 <= ny < n:
                    if space[nx][ny] == 0:
                        space[nx][ny] = v_i
                        q.append((v_i, nx, ny, v_s + 1))
                        
space[x-1][y-1]

원래는 x,y 좌표만 큐에 넣었지만 virus number, x, y, time 네가지를 모두 큐에 넣었더니 잘 동작이 되었다 ! 

   - 조건에서 사용할 변수는 웬만하면 큐에 다 넣어야겠다 

   - 그리고 큐에 한번에 여러개의 입력을 넣어도 되나? 해서 이렇게 푼거였는데 충분히 가능했던것임,, (바보,,,)

   - 그래도 로직은 맞아서 내 코딩실력에 다시 한번 실망하기도 하고 희망을 보기도 한 하루다!!

 

나는 바이러스 좌표를 하나의 리스트에 모으고 이 리스트를 for문을 돌며 bfs를 돌았다

아래 코드는 바이러스 좌표를 한번에 큐에 넣고 풀이하는 방법이다 

 

그리고 바이러스 리스트를 만들때도 나는 처음부터 k개의 원소를 가지는 2차원 배열을 만들어 해당 인덱스에 좌표를 넣었는데 해설에는 그냥 space를 돌고 sort하는 방법을 썼다

   - 여기서 시간이 쪼금 걸렸는데 나도 이렇게 하면 되겠다고 하나 또 배웠다

 

👇 최종!!

from collections import deque
n, k = 3, 3
s, x, y = 2, 3, 2

space = [[1, 0, 2],
        [0, 0, 0],
        [3, 0, 0]]

virus = []

## virus위치 리스트 만들기 (index = virus num)
for i in range (n):
    for j in range (n):
        if space[i][j] != 0:
            virus.append((space[i][j],i,j,0))  ## 바이러스, x, y, 시작 시간

virus.sort()
q = deque(virus)

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

while q:
    vi, vx, vy, vs = q.popleft()
    if vs == s:
        break
    
    for i in range (4):
        nx = vx+dx[i]
        ny = vy+dy[i]
        if 0 <= nx < n and 0 <= ny < n:
            if space[nx][ny] == 0:
                space[nx][ny] = vi
                q.append((vi, nx, ny, vs+1))   
                
space[x-1][y-1]

연습문제 풀이는 깃허브에도 업로드 되어있습니다 

GitHub - gymin97/algorithm_study: Solve the algorithm problems (python3)