[알고리즘] 백준 18221 파이썬 - 교수님 저는 취업할래요

반응형

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

문제

성규는 학점이 높고 알고리즘도 잘 다루는 편이라 매년 알고리즘 대회에 나가 수상을 해오곤 한다. 성규의 꿈은 대학교 4학년 칼졸업을 하고 나서 좋은 대기업에 취직하여 빨리 돈을 버는 것이다.

어느 날, 성규는 전공 수업을 들으러 강의실에 가서 책을 펴고 앉았다. 이 때 교수님이 수업을 시작하시기 전에 한 말씀 하셨다.

교수님: "음... 여기서 내가 눈 여겨 봐온 학생이 있는데... 그래, 성규야. 너 내 랩실에 들어올 생각 없니? 나와 함께 알고리즘에 대한 논문이나 써보자꾸나."

성규는 큰일이다 싶었다. 성규는 졸업하고 싶었다. 대답을 할 생각이 떠오르기 전에 먼저 도망가야겠다는 생각이 들어버렸다!

강의실에는 가로로 N 행, 세로로 N 열, 총 N × N 개의 책상이 있으며, 위쪽에서부터 R 번째 행, 왼쪽에서부터 C 번째 열에 있는 책상의 위치를 (R, C)로 표현한다. 각 책상 자리는 비어있거나, 성규가 아닌 학생 혹은 성규가 앉아있거나, 교수님이 위치해 있다.

도망가는 데 성공하려면, 성규와 교수님의 거리가 5 이상이면서, 교수님과 성규를 꼭짓점으로 하는 축에 평행한 직사각형 안에, 교수님을 제지해줄 성규가 아닌 학생이 세 명 이상 있어야 한다.
단, 교수님과 성규가 같은 행 혹은 같은 열의 책상에 앉아있다면 교수님과 성규를 잇는 선분 상에 성규가 아닌 학생이 세 명 이상 있어야 한다.

이때, 책상 (a, b)와 책상 (c, d) 간의 거리로 정의한다.

성규는 도망가다가 잡히는 것이 최악이라 판단되어, 도망갈 수가 없는 환경이면 순순히 대학원생의 길로 들어서려고 한다. 이런 성규를 위해 확실히 도망갈 수 있는지 알려주는 프로그램을 작성하자.

 

문제풀이

n=int(input())
List=[]
tmp=[]
for i in range(n):
	#01
    a=list(map(int,input().split()))
    for j in range(len(a)):
        if a[j]==5 or a[j]==2:
            tmp.append([i,j])       
    List.append(a)
#02
x=((tmp[0][0]-tmp[1][0])**2+(tmp[0][1]-tmp[1][1])**2)**0.5
if x>=5:
    tmp.sort()
    #03
    x,y=min(tmp[0][1],tmp[1][1]),max(tmp[0][1],tmp[1][1])
    cnt=0
    for i in range(tmp[0][0],tmp[1][0]+1):
        for j in range(x,y+1): 
            if List[i][j]==1:
                cnt+=1
    #04
    if cnt>=3:
        print(1)
    else:
        print(0)
else:
    print(0)

- #01 : a를 입력받아서, for문을 통해 5와 2의 위치를 찾으면

           해당 좌표를 tmp에 추가해준다. 이후 a는 List에 각각 추가한다.

- #02 : 아까 구한 5와 2의 위치가 있는 tmp 좌표 2개의 거리를 x에 저장한다.

           만약 x가 5이상이면 그 다음 조건으로 넘어가고,

           그렇지 않으면 0을 출력하고 종료한다.

- #03 : x,y에 각각 tmp[0][1],tmp[1][1] 중 작은 값과 큰 값을 저장한다.

           i와 j를 이용해 5와 2 사이에 존재하는 직사각형 크기의 범위를

          반복문으로 돌며 만약 List[i][j]가 1인 값이라면 cnt를 1 추가한다.

- #04 : 최종적으로 cnt가 3이상이면 1을 출력, 그렇지 않으면 0을 출력한다.