문제
출처: https://www.acmicpc.net/problem/18405
나의 접근법
위 문제는 이것이 코딩테스트다 with 파이썬 에 수록된 문제입니다. 먼저 답을 읽지 않고 제 스스로 풀어보려고 노력했습니다.
바이러스의 위치를 x,y좌표로 기억하여 번호 마다 리스트에 저장하였습니다. 그리고 시간 S 만큼 반복하여 바이러스를 퍼뜨렸습니다.
일반 케이스 말고 특이 케이스도 생각해봤습니다.
- 만약 1번 바이러스가 2번 나오면 어떡하지?
만약 1~K번의 바이러스가 연속으로 나오지 않고 랜덤으로 나오면 어떡하지?
저는 위와 같은 경우의 수도 고려하며 풀려고 노력했습니다.
첫번째 풀이법
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import sys
from collections import deque
def BFS(virus, virusPositions):
for i in range(len(virusPositions[virus])):
a, b = virusPositions[virus].pop(0)
for j in range(4):
nx = a + dx[j]
ny = b + dy[j]
if nx >= 0 and nx < N and ny >= 0 and ny < N:
if virusGraph[nx][ny] == 0:
virusGraph[nx][ny] = virus
virusPositions[virus].append([nx, ny])
virusGraph = []
N, K = map(int, sys.stdin.readline().split())
for i in range(N):
virusGraph.append(list(map(int, sys.stdin.readline().split())))
virusPositions = [[] for _ in range(N+1)]
for i in range(N):
for j in range(N):
if virusGraph[i][j] != 0:
virusPositions[virusGraph[i][j]].append([i, j])
S, X, Y = map(int, sys.stdin.readline().split())
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
for i in range(S):
for virusNum in range(1, K+1):
if not virusPositions[virusNum]:
continue
BFS(virusNum, virusPositions)
print(virusGraph[X-1][Y-1])
위 코드는 제가 처음으로 제출한 것입니다.
예시는 맞았지만 IndexError가 발생했습니다. print()로 로그를 찍어가며 문제점을 몇시간 동안이나 찾았지만 결국 잡아 내지 못했습니다. 그래서 구글링과 블로그를 찾아가며 저와 비슷하게 IndexError가 발생한 경우를 찾아보았습니다. 하지만 IndexError는 거의 찾아볼 수 없었고 저는 백준에서 게시판이라는 곳에서 18405번 문제 중 IndexError에 대한 글을 남긴 내용을 찾아봤습니다.
딱 1개 있었지만 답변은 없었습니다..
하는 수 없이 저는 제 코드를 남기고 질문을 남겼습니다. 질문의 주소는 다음과 같습니다. https://www.acmicpc.net/board/view/85776#comment-139171
몇 시간 안되어 nasoob114 님께서 바로 답변을 달아주셨고 반례를 들어주며 왜 틀렸는지도 알려주셨습니다.
위 답변을 통해 저는 코드를 바로잡을 수 있었고 반례도 통과할 수 있었습니다. nasoob114 님께 정말 감사드린다고 또 한 번 전하고 싶습니다. 덕분에 며칠 씨름해도 못풀 문제를 단숨에 해결할 수 있었습니다.
그 반례는 다음과 같습니다.
2 3
3 0
1 2
0 1 1
K가 항상 N보다 작거나 같을 경우의 수만 생각했습니다. 하지만 K가 N보다 큰 경우는 생각하지 못했습니다.
이 경우 virusPositions[virusGraph[i][j]].append([i, j]) 에서 index error 가 발생합니다.
virusPositions[virusGraph[i][j]]에서 K가 N 보다 클 수도 있기 때문에 인덱스 에러가 발생하는 것이었습니다.
위 코드를 수정하여 2번째 코드를 작성하고 제출하였습니다.
두번째 제출 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import sys
from collections import deque
def BFS(virus, a, b, s):
#for i in range(len(virusPositions[virus])):
for j in range(4):
nx = a + dx[j]
ny = b + dy[j]
if nx >= 0 and nx < N and ny >= 0 and ny < N:
if virusGraph[nx][ny] == 0:
virusGraph[nx][ny] = virus
virusPositions.append([virus, nx, ny, s+1])
virusGraph = []
N, K = map(int, sys.stdin.readline().split())
for i in range(N):
virusGraph.append(list(map(int, sys.stdin.readline().split())))
virusPositions = []
for i in range(N):
for j in range(N):
if virusGraph[i][j] != 0:
#바이러스 번호, 바이러스 좌표, 시간
virusPositions.append([virusGraph[i][j], i, j, 0])
virusPositions.sort(key=lambda x: x[0])
virusPositions = deque(virusPositions)
S, X, Y = map(int, sys.stdin.readline().split())
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
#S초만큼만 반복
for i in range(S):
for j in range(1, K+1):
virusNum, x, y, s = virusPositions.popleft()
BFS(virusNum, x, y, s)
print(virusGraph[X-1][Y-1])
바이러스 번호를 인덱스로 사용하여 위치를 저장하지 않고, append()를 사용해서 번호와 위치, 그리고 초 까지 한번에 입력시키고 정렬하였습니다. 리스트를 큐로 사용하여 가장 먼저 들어간건 pop(0)로 가장 먼저 꺼내는 방식을 이용하여 문제를 해결했습니다.
하지만 이 경우에도 IndexError가 발생하였습니다. 솔직히 이 때 그냥 접고 책이랑 똑같이 제출하고 싶었습니다. 하지만 이 경우 제가 놓친 무언가가 있을 것 같다고 생각하고 책에나온 풀이와 제 코드를 다시 한 번 코드를 분석했습니다.
차이점은 쉽게 찾을 수 있었습니다. 저는 for i in range(S)로 입력된 시간만큼 반복문을 실행하며 virusPositions에서 데이터를 가져오는 방식이었습니다.
그런데 이경우 아래와 같은 예시처럼
2 4
3 4
0 2
10 1 1
1초만에 모든 그래프에 바이러스가 퍼져 더 이상 virusPositions 정보가 없는데 계속 popleft()해서 IndexError가 발생하는 것이었습니다.
그래서 저의 풀이는 완전 틀렸다는 것을 깨닫고서야 책과 비슷하게 답을 작성했습니다. 하지만 책을 베끼진 않았고 왜 그렇게 풀었는지 그제서야 이해할 수 있었습니다.
아래는 마지막으로 제가 제출한 코드입니다.
세번째 제출 코드 (최종)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import sys
from collections import deque
def BFS(virus, a, b, s):
for j in range(4):
nx = a + dx[j]
ny = b + dy[j]
if nx >= 0 and nx < N and ny >= 0 and ny < N:
if virusGraph[nx][ny] == 0:
virusGraph[nx][ny] = virus
virusPositions.append([virus, nx, ny, s+1])
virusGraph = []
N, K = map(int, sys.stdin.readline().split())
for i in range(N):
virusGraph.append(list(map(int, sys.stdin.readline().split())))
virusPositions = []
for i in range(N):
for j in range(N):
if virusGraph[i][j] != 0:
#바이러스 번호, 바이러스 좌표, 시간
virusPositions.append([virusGraph[i][j], i, j, 0])
virusPositions.sort(key=lambda x: x[0])
virusPositions = deque(virusPositions)
S, X, Y = map(int, sys.stdin.readline().split())
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
#S초만큼만 반복 => 이렇게 하면 10 초가 넘어가면 pop이 비어있음
while virusPositions:
if virusGraph[X-1][Y-1] != 0:
break
virusNum, x, y, s = virusPositions.popleft()
if s == S:
break
BFS(virusNum, x, y, s)
print(virusGraph[X-1][Y-1])
백준 결과
백준 결과입니다. 10번만에 정답을 맞을 수 있었습니다. 출력 초과는 제가 log를 찍기위해 print함수를 중간중간에 넣어놓았는데 그걸 지우지 못하고 바로 제출해서 에러가 난 경우로 실제는 8번 만에 맞았습니다.
계속 IndexError가 뜰 때마다 세상이 저를 속이는 것 같았습니다. 하지만 문제를 다 맞추고 이제서야 돌이켜 보니 결국 문제는 제 스스로에게 있었습니다.
후기 및 다짐
백준이나 코테 문제는 대부분 모범 답안과 문제에 딱 적용되는 몇 가지 알고리즘과 코드 디테일이 정해져 있는 것 같습니다. 하지만 저는 일단 문제를 제스스로 풀어보고 안풀리면 답을 보는 과정을 들이고 있습니다.
제가 알고리즘 능력을 기르기 위해 백준 문제를 푼지 2달 조금 안되는데 벌써부터 답을 보고 클린코드와 모법답안과 같은 코드를 짜는 것은 요행을 바라는 것 같아서 지금은 시간이 매우 많이 걸리더라도 답을 보지 않고 먼저 문제푸는 힘들 기르려고 노력하고 있습니다.
그런데 오늘 이 문제하나 푸는데 시간을 다 보냈기 때문에 꼬박 하루 걸렸습니다. 아직은 실력이 많이 부족하여 시간대비 문제푸는 양이 너무 적은 것 같습니다.
이렇게 까지 고생을 하며 18405번 문제를 풀었는데도 불구하고 정답이라고 출력되었을때 그렇게 기쁘지 않았습니다. 순수하게 제 실력 100%로 풀지 못해서 아쉬움이 커서 그런 것 같습니다. 하지만 왜 틀렸는지 어디가 문제였는지 자세하게 알고 넘어가서 그부분은 하나로 이 시간들이 매우 아깝지는 않았습니다.
다음 문제를 풀 때는 에러가 발생하더라도 꼭 문제의 원인을 스스로 찾아 해결해보도록 하겠습니다.