머쓱이는 '생명 게임'이라고 알려진 프로그램을 만들려고 합니다. 생명 게임은 2차원 보드에서 이루어지며, 각각의 칸은 0이 저장된 죽은 칸이거나 1이 저장된 살아있는 칸입니다. 이때 자기 자신의 값과 주변 이웃한 칸들의 값에 따라 다음 세대에서 각 칸의 값이 정해집니다. 머쓱이가 만든 생명 게임의 규칙은 다음과 같습니다.
살아있는 칸 주변에 이웃이 2명 이하로 존재하면 그 칸은 다음 세대에 죽는다
살아있는 칸 주변에 이웃이 5명 이상 존재하면 그 칸은 다음 세대에 죽는다
죽어있는 칸 주변에 이웃이 정확히 2명 존재하면 그 칸은 다음 세대에 살아난다.
그 이외의 경우에는 살아있거나 죽은 상태가 유지된다.
검사 할 점의 개수n과 처음 보드의 상태board, 점의 좌표를 나타내는 정수쌍[a,b]가n개 담긴 리스트position이 주어졌을 때, 한세대 뒤에board[a][b]칸의 상태 리스트를 return하는 함수를 완성해주세요.
제한사항
1 ≤n≤ 40
3 ≤board의 길이 ≤ 20
3 ≤board[i]의 길이 ≤ 20
board[i][j]의 값은0또는1
board는 직사각형 모양입니다.
position의 길이 = n
position[i]는 [a, b] 형태로 칸의 좌표를 나타냅니다.
0 ≤ a <board의 길이
0 ≤ b <board[0]의 길이
입출력 예
입출력 예 설명
입출력 예 설명 #1
0세대의 보드와 1세대의 보드는 다음과 같습니다.
입출력 예 설명 #2
0세대의 보드와 1세대의 보드는 다음과 같습니다.
-
[PCCE 모의고사 2] 10번 문제 풀이
이 문제는 2차원 리스트를 다룰 수 있는지에 관한 문제에요. 2차원 리스트의 각 항목들이 서로에게 영향을 미치면서 값이 바뀌는 흐름을 잘 좇을수 있느다면 쉽게 풀리는.. 문제는 아닙니다.
2차원 리스트에 대해 이해하고 있다고 해도 문제를 풀다 보면 난관에 부딪힐 건데요, 어떤 난관이 도사리고 있는지 살펴보도록 할까요?
-
문제 풀 준비
문제의 핵심은 해당 위치에 있는 항목과 그 주변 (상하좌우와 대각선)의 여덟 개의 항목을 비교하는데 있습니다. 하나의 값과 그 주변만 비교하는 문제라면 쉬웠을 거예요. 아래의 그림은 3*3 2차원 리스트에서 p의 위치를 [a][b]라 했을 때 그 주변 항목들의 인덱스를 나타낸 표에요.
만약 친구들이 그림을 이해할 수 있다면 이 문제를 풀 수 있을거에요. 반복문을 사용해 p와 주변 값들을 비교할 수 있을테니까요. 위와 같은 2차원 리스트의 항목들을 전부 출력하려면 2중 for문을 사용하면 될거예요. 아래의 코드를 볼까요?
3*3 2차원 리스트의 모든 항목들을 출력하기 위한 코드를 잠깐 살펴 봤어요. 그런데 만약 어떤 위치의 좌표값이 주어지고, 그 주변의 3*3 항목들을 출력하라고 한다면 어떻게 코드를 짜야 할까요?
예를 들어 [[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]] 와 같은 5*5 리스트에서 정중앙에 있는 13의 좌표 [2][2]가 주어질 경우에는 13을 둘러싼 7, 8, 9, 12, 13, 14, 17, 18, 19를 출력해야 하는 것이죠. 아래의 코드 에디터에서 친구들이 직접 '?' 자리에 코드를 작성해서 출력해 볼까요? p의 위치는 [2, 2]와 같이 리스트의 형태로 주어지구요.
p가 주어졌으니 p를 활용해야 돼요. p를 포함해서 p 주변의 값들의 좌표를 먼저 살펴보면,
[1][1], [1][2], [1][3] 그리고
[2][1], [2][2](이놈이 p), [2][3]
마지막으로 [3][1], [3][2], [3][3] 이 될 거예요.
이 좌표값들을 p를 활용해서 나타내 볼까요?
[p[0]-1][p[1]-1], [p[0]-1][p[1]], [p[0]-1][p[1]+1] 그리고
프로그래밍도 마찬가지로, 어느 순간 부터는 코드를 구현해 내는 기술적 능력 보다는 창의적인 아이디어가 필요한 경우가 생겨요. 이번 문제가 바로 그렇죠.
-
우리에게도 마찬가지로 판(board)가 주어져있어요. 다행히도 이 판때기는 우리가 맘대로 가지고 놀 수 있는 판때기죠. 그래서 저는 이 판때기를 확장해 보기로 했어요. 아래의 그림처럼요.
만약 3*3 2차원 리스트가 주어진다면 상하좌우로 확장해서 5*5 2차원 리스트로 만드는 것이죠. 왜? 그래야 모서리나 꼭짓점을 신경쓸 필요가 없어지니까요. 이렇게 판때기를 확장시켜 놓으니 특정 위치의 그 주변의 항목들을 비교하기 편해졌어요.
문제에서 두 번째 입출력 예를 볼까요? board가 [[0, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 1], [0, 1, 0, 1], [1, 1, 1, 0], [0, 0, 0, 1]] 로 주어져요. 4*6 2차원 리스트네요. 이 판때기의 상하좌우를 확장해서 6*8 2차원 리스트로 만들어 볼게요.
판때기를 확장할 때 항목들의 값은 0으로 정해줄게요. 항목의 값이 0이어야 다른 항목들에 영향을 미치지 않거든요. 문제에서는 p 주변의 1들을 더해서 어쩌구 저쩌구~ 였는데, 0은 덧셈의 항등원이니 판때기를 0으로 확장한다고 해서 덧셈에 영향을 미치지 않겠죠?
board를 확장하려면 리스트의 함수 insert()와 append()를 사용하면 쉽게 할 수 있어요. 아래의 코드를 볼까요?
반복문을 통해 board의 각 항목 맨 앞과 뒤에 0을 넣었어요. 그리고 board 자체에 0으로만 이루어진 리스트를 맨 앞과 뒤에 추가해 주었죠. 쉽게 말해, 0으로 둘러쌓았다고 할 수 있어요.
이렇게만 코드를 짜 주어도 문제의 90%는 풀었다고 할 수 있어요. 나머지는 간단하죠. position을 통해 위치값이 주어지기 때문에 position의 항목들과 그 주변 값들을 비교해주기만 하면 돼요.
만약 p가 [1][3]이라면 그 주변 8개 값을 문제의 조건과 비교하여 검사하기만 하면 되겠죠?
-
문제 풀이
문제에서는 1이 살은 것이고 2가 죽은 것이라고 하네요. 특정 위치(p라고 할게요)의 값이 1이라면
'p 주변에 1이 2개 이하거나 5개 이상이면 p는 다음 세대에 0이 된다. 그렇지 않으면 그대로 1이다.' 라고 하고 있어요.
만약 p가 0이라면 주변에 1이 2개 여야만 다음 세대에 1이 될 수 있구요. 그렇지 않으면 그대로 0이 되겠죠? 정리하면,
p가 1인 경우
- 주변에 1이 2개 이하거나 5개 이상 ☞ 다음 세대에 0이 됨
- 그렇지 않으면 ☞ 다음 세대에 그대로 1
p가 0인 경우
- 주변에 1이 2개 ☞ 다음 세대에 1이 됨
- 그렇지 않으면 ☞ 다음 세대에 그대로 0
이 되겠죠. 조건문으로 쉽게 나타날 수 있겠네요. 하지만 조건문으로 나타내려면 주변에 1이 몇 개 인지 알아야 돼요.
-
이제 우리는 p 주변에 1이 몇 개 있는지 알아보기 위한 코드를 만들어 볼거에요. p의 위치만 알면 p를 중심으로 한 3*3 범위를 다루는 것을 할 수 있었잖아요? 만약 p의 위치가 [1][3]일 때 p를 중심으로 한 3*3의 범위를 출력해 볼까요? 위~ 에서 만든 코드를 적용하면 쉽게 코드를 짤 수 있어요.
주의할 것은 board를 확장 시켜 놓았기 때문에 p의 위치가 [1][3]이 아니라는 것이에요. 상하좌우로 1칸씩 늘어났기 때문에 p의 위치도 1칸씩 밀려났겠죠? 그 위치를 a, b라고 놓는다면 아래의 코드와 같이 작성할 수 있어요.
코드를 출력해 보면 000 100 010 과 같은 값이 출력되는 것을 볼 수 있어요. p를 포함한 3*3 항목들의 값이죠. 이제 이 3*3 범위의 값들을 다 더해 줄 거예요. 왜? 문제에서는 이웃(주변)에 1이 몇 개 있는지 요구하고 있는데, 바꿔 말하면 그냥 다 더하라는 것과 같아요. 1이 두 개 있는 것과 1 더하기 1은 같잖아요? p를 포함하겠지만 일단 3*3의 항목들을 다 더해보죠.
t라는 변수에 항목들의 값을 다 더한 다음 출력해 보았어요. 2가 출력되는 것을 볼 수 있어요. 당연하죠? board에서 p가 위치한 [1][3]을 중심으로 한 3*3에서는 1이 2개 밖에 없으니까요. 마찬가지로 [5][3]을 중심으로 한 3*3의 1의 개수도 구할 수 있어요. 아래의 코드 처럼 p의 값만 바꿔주면 돼죠.
이번에도 역시 2가 출력되는 것을 볼 수 있어요. p 주변에는 1이 한 개 밖에 없지만, p 자신이 1이기 때문에 2가 출력된 것이죠.
-
이제 p를 중심으로 한 3*3의 값들을 다 더해 놓았으니 조건문으로 비교만 해주면 문제가 풀리겠어요! 젤 쉬운 것만 남았네요. 아래의 코드를 볼까요?
코드가 길어서 복잡해 보이지만 내용은 별게 없죠. p를 포함하여 3*3의 항목들의 합산을 가지고 조건문을 만든거니까요. p가 1일땐 주변의 값이 2이하이거나 5이상이면 다음 세대에 죽을거예요. 그런데 p 자체가 1이기 때문에 조건문의 조건에서 각각 1씩 더해줄 필요가 있었어요. p가 1이라 1이 더 많이 더해진 상태니까요.
나머지는 굉장히 간단한 조건문으로 만들 수 있을거구요.
마지막으로 이 문제를 풀기 위해 position의 항목들을 p라고 놓고 반복문에 적용해 보면, 아래와 같이 코드를 작성할 수 있겠어요.
이 코드가 가장 이상적인 답은 아닐 수 있어요. 하지만 주어진 틀을 넘어서 사고를 확장하는 방법을 배울 수 있다면, 그것 만으로도 배울 점이 있겠죠?
