[백준]_18221번 : 교수님 저는 취업할래요

18221번: 교수님 저는 취업할래요

개인적으로 설정 자체가 너무 웃겨서 가장 재밌게 풀었던 문제 중 하나로 손꼽힌다 하지만 필자는 대학원 지망생... 얼핏 문제를 보기에는 성규와 교수님 사이의 거리, 성규와 교수님이 각 직사각형의 꼭짓점을 이루는 직사각형 안에 있는 다른 학생(1)들의 수만 고려해 주면 되는 간단한 문제처럼 보인다. 하지만 필자는 이 문제를 무려 6번이나 심지어 파이썬으로!! 틀리고 나서야 정답을 출력받을 수 있었다. 이 글을 보고 있는 사람들은 나와 같은 실수를 하지 않기를 바라며 가장 중요한탈출 조건들을 나열하겠다.

---

탈출 조건

• 교수와 성규의 직선거리는 5 이상이다(필자는 이 조건을 읽고 나중에 코드를 짤 때 거리 계산을 숫자의 개수로 치환해 버려서 틀렸다. 예를 들어 { 5, 0, 0, 0, 2 }은 거리가 4이다. 하지만 거리를 숫자의 개수로 파악하게 되면 거리를 5로 착각하게 된다)
•  교수가 2 사분면, 성규가 4 사분면에 존재하리라는 보장은 없다. 이것이 왜 중요하냐고? 누구의 행, 열 좌표가 더 크냐에 따라 두 번째 조건을 조사할 때 누구의 좌표에서 누구의 좌표를 뺀 상태로 반복문을 돌릴지 알아야 된다

---

전략

• 먼저 교수와 성규 사이의 거리가 5 이상인지 체크한다. 왜냐하면 그 둘 사이에 아무리 학생수가 많아도 거리가 5 이상이 아니라면 무용지물이기 때문에 거리 조건이 제1 검사 대상이다.
• 그다음으로 교수와 성규가 이루는 직사각형 안에 있는 학생들의 수를 세어줄 것이다. 물론 교수와 성규가 한 직선에 있을 때도 계산할 수 있게 만들어줄 것이다. 

---

시도 1(Python)

size=int(input())
prof=[]
slave=[]
room=[]
for _ in range(size):
    room.append(list(map(int, input().split()[:size])))
row=0
for el in room:
    if el.count(5):
        prof.append(row)
        prof.append(el.index(5))
    if el.count(2):
        slave.append(row)
        slave.append(el.index(2))
    row+=1
#
if (prof[0]-slave[0])**2+(prof[1]-slave[1])**2<25:
    print(0)
else:
    cnt_ones=0
    min0 = prof[0]
    max0 = slave[0]
    min1 = prof[1]
    max1 = slave[1]
    if prof[0]>slave[0]:
        max0=prof[0]
        min0=slave[0]
    if prof[1]>slave[1]:
        max1=prof[1]
        min1=slave[1]
    for row in range(min0,max0+1):
        for col in range(min1,max1+1):
            if room[row][col]==1:
                cnt_ones+=1
    if cnt_ones<3:
        print(0)
    else:
        print(1)

<평가> 파이썬 코드가 맞나 싶을 정도로 너무 길고 조잡하다;; 그 당시에는 너무 답을 도출하는 데에 치중해서 이런 대참사가 벌어진 게 아닌가 싶다.. 불필요한 요소들을 대거 수정해 보자.

 

수정

import sys

이 당시에는 import sys도 모르고 있던 시절이었다.. 빠른 전달을 위해 sys를 사용해 준다.

import sys
input=sys.stdin.readline
size=int(input())

 

row 생략

여기서 말하는 row는 초반에 나온 row를 말하는 것이다. row를 도입한 이유는 교수와 성규의 위치 좌표를 행과 열로 나타내기 위해서이고 특히 row는 행을 알아내기 위해서 추가했다. 하지만 새로운 변수들 선언하지 않고서도 행 인덱스를 알 수 있다.

for el in room:
    if el.count(5):
        prof.append(room.index(el))
        prof.append(el.index(5))
    if el.count(2):
        slave.append(room.index(el))
        slave.append(el.index(2))

위와 같이 el을 그냥 room에서 인덱싱 해주면 된다. 이렇게 했을 때와 row 변수를 추가해 행 요소를 찾는 것을 비교해 보면 대략 전자의 경우가 32ms 더 빠르다.

하지만 이 방법 말고도 코드 길이를 줄이는 방법이 있다. 그것은 바로 extend!!

for el in room:
    if el.count(5):
        prof.extend([room.index(el), el.index(5)])
    if el.count(2):
        slave.extend([room.index(el), el.index(2)])

이렇게 하면 extend 대상 리스트에 이중 리스트로 들어가는 것이 아닌가 생각할 수 있지만 extend는 리스트와 리스트를 이어주는 역할을 해주기 때문에 [ ] + [ 2, 3 ] = [ 2, 3 ]의 양상을 띤다. 

참고로 위의 방법과 시간 차이가 나지는 않는다. 

누가 더 큰가?

위 코드를 가장 불편하게 만드는 부분인 else: 에 들어 있는 코드를 조금 손봐주자. 위에서는 조건문을 이용해 누가 더 큰지 알아내었지만 파이썬에는 내장 함수로 min과 max가 있다!! 참고로 0이 붙은 변수는 행 관련 변수이고 1은 열 관련 변수이다. 따라서 abs(절댓값)을 짬뽕하면 아래와 같은 코드를 얻을 수 있다.

else:
    cnt_ones=0
    min0=min(prof[0],slave[0])
    min1=min(prof[1],slave[1])
    for row in range(min0,min0+abs(prof[0]-slave[0])+1):
        for col in range(min1,min1+abs(prof[1]-slave[1])+1):
            if room[row][col]==1:
                cnt_ones+=1
    if cnt_ones<3:
        print(0)
    else:
        print(1)

abs를 사용해서 최댓값을 구하나 max를 사용해서 구하나 시간이 똑같이 224ms가 걸려서 새로운 느낌을 주고자 abs를 한 번 써보았다. 따라서 최종 코드는 아래와 같다.

import sys

input = sys.stdin.readline
size = int(input())
prof, slave, room = [], [], []
for _ in range(size):
    room.append(list(map(int, input().split()[:size])))
for el in room:
    if el.count(5):
        prof.extend([room.index(el), el.index(5)])
    if el.count(2):
        slave.extend([room.index(el), el.index(2)])
if (prof[0] - slave[0]) ** 2 + (prof[1] - slave[1]) ** 2 < 25:
    print(0)
else:
    cnt_ones = 0
    min0 = min(prof[0], slave[0])
    min1 = min(prof[1], slave[1])
    for row in range(min0, min0 + abs(prof[0] - slave[0]) + 1):
        for col in range(min1, min1 + abs(prof[1] - slave[1]) + 1):
            if room[row][col] == 1:
                cnt_ones += 1
    if cnt_ones < 3:
        print(0)
    else:
        print(1)

---

시도 2(C)

#include <stdio.h>
#include <stdlib.h>
int distance(int x1, int y1, int x2, int y2){
    if((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)<25) return 1;
    else return 0;
}
int main() {
    int size;
    int prof[2]={0};
    int slave[2]={0};
    scanf("%d", &size);
    int** matrix = (int**)malloc(size * sizeof(int*));
    for (int i = 0; i < size; i++) {
        matrix[i] = (int*)malloc(size * sizeof(int));
    }
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            scanf("%d", &matrix[i][j]);
            if (matrix[i][j]==5){
                prof[0]=i; 
                prof[1]=j;
            }
            if (matrix[i][j]==2){
                slave[0]=i; 
                slave[1]=j;
            }
        }
    }
    if(distance(prof[0], prof[1], slave[0], slave[1])) printf("0");
    else{
        int cnt_ones=0;
        int min0=(prof[0]>slave[0] ? slave[0] : prof[0]);
        int min1=(prof[1]>slave[1] ? slave[1] : prof[1]);
        for(int row=min0;row<min0+abs(prof[0] - slave[0])+1;row++)
            for(int col=min1;col<min1+abs(prof[1] - slave[1])+1;col++)
            {
                if (matrix[row][col]==1)
                    cnt_ones+=1;
            }
        if (cnt_ones<3) printf("0");
        else printf("1");
    }
    for (int i = 0; i < size; i++) {
        free(matrix[i]);
    }
    free(matrix);
    return 0;
}

<해석>

초반에 나오는 distance 함수는 이후 교수와 성규 사이의 거리를 측정하기 위해  사용될 것이다. 그 둘 사이의 거리의 제곱이 25 미만이면 1을 반환하여 if(distance(prof[0], prof[1], slave[0], slave[1])) printf("0"); 를 작동시켜 준다.

 

동적 할당을 통해 size * size 배열을 선언해주고 그 안에 값들을 대입한다. 대입과 동시에 교수와 성규의 위치를 파악해 prof[ ], slave[ ] 좌표에 넣어준다. 여기서 주의!! 만약 이때의 조건문을 아래와 같이 짠다면 낭패를 볼 것이다.

if (matrix[i][j]==5){
    prof[0], prof[1] = i, j; 
}
if (matrix[i][j]==2){
    slave[0], slave[1] = i, j; 
}

별 문제없어 보이는 코드이다! 두 줄로 작성할 것을 한 줄로 작성했으니 얼마나 깔끔한가? 하지만 이런 접근은 콤마(,)의 기능을 무시한 것이다. 만약 matrix[ 2 ][ 3 ]==5 이라고 가정하자. 따라서 prof[ 0 ] 과 prof[ 1 ] 에는 각각 2와 3이 대입되어야 한다. 하지만 현실은 prof[ 1 ]에만 2가 대입된다. 왜냐하면 한 줄에 콤마 연산을 모두 때려박을 경우 첫째 값(2)을 첫 번째 변수에 evaluate 하지만 결과는 버린다. 결국 다음 변수로 넘어가고 마지막 변수(두 번째 변수)에 도달하고 나서야 2를 대입시킨다. 따라서 위의 C코드처럼 한 줄마다 변수에 값을 대입해 줘야 한다.

 

마지막으로 삼항연산자인 (condition ? expression1 : expression2)와 abs()를 이용하여 성규를 제외한 학생(1) 들을 찾아주었다.