[코드업 기초 100제 1099번] 성실한 개미

개미는 뚠뚠 오늘도 뚠뚠 열심히 코딩 하네

 

 

대망에 마지막 문제이기에 풀이를 남겨두려고 한다.

[문제 설명]

경곽이는 생물 분야에 관심이 생겨 개미를 연구하고 있었는데,

유원지에서 연구 주제인 왕개미를 발견하게 되었다.

왕개미를 유심히 살펴보던 중 특별히 성실해 보이는 개미가 있었는데,

그 개미는 개미굴에서 나와 먹이까지 가장 빠른 길로 이동하는 것이었다.

개미는 오른쪽으로만 움직이다가 장애물을 만나면 아래쪽으로 움직여 가장 빠른 길로 움직였다.

(오른쪽으로 길이 있으면 다시 오른쪽으로 움직인다.)

이에 호기심이 생긴 경곽이는 그 개미를 미로 상자에 넣고 살펴보기 시작하였다.

미로 상자에 넣은 개미는 먹이를 찾았거나, 더 이상 움직일 수 없을 때까지 오른쪽 또는 아래쪽으로만 움직였다.

미로 상자의 구조가 0(갈 수 있는 곳), 1(벽 또는 장애물)로 주어지고,

먹이가 2로 표시되어 주어질 때, 똑똑한 개미의 이동 경로를 예상해보자.

단, 가장 아래의 가장 오른쪽에 도착한 경우나, 더 이상 움직일 수 없는 경우, 또는 먹이를 찾은 경우에는 그 곳에 머무른다고 가정한다.

미로의 테두리는 모두 벽으로 되어있으며, 개미집은 반드시 (2, 2)에서 시작된다.

 

[입력]

10 * 10 크기의 미로 상자의 구조와 먹이의 위치가 입력된다.

 

[출력]

성실한 개미가 이동한 경로를 9로 표시해 출력한다.

 

 

 

10x10의 배열이 주어지고 마치 태두리를 입은것 마냥 마지막은 1로 채워져 있다.

사실 저건 입력에서 해결해야하는 부분임으로 우리가 크게 신경써도 되지 않아도 된다.

 

그럼 가장 먼저해야할 것은 역시 입력을 옳바르게 받는 것이다.

 

 

 

road = []
for i in range(0, 10):
    buf = input().split()
    road.append(buf)
#print(road)

입력받을 길을 생성해주자.

어차피 10x10임으로 10번 반복해서 입력을 해준다.

처음 행을 split해주어 list형태의 buf를 생성한뒤 road에 넣어서 2차원 배열을 구성해준다.

역시 만든 후에는 잘 입력을 받는지 출력도 해본다.

 

 

이 후에는 구성을 생각해봐야한다.

일단 개미가 움직인다.

하지만 개미를 직접적으로 표현하기엔 너무 복잡해진다.

그저 우리는 키보드 커서가 움직이듯이 좌표를 움직이며 숫자를 바꿔가야할 것이다.

그래서 x,y라는 좌표를 계속 수정해가면서 마치 키보드커서가 데이터를 훑어가듯이 이동시켜주는 방식을 생각했다.

x,y좌표에 값이 2라면 9로 바꾸고 break

0이라면 9로 바꾸고 다음 나아갈 방향을 잡기위해 if문을 통해서 우선순위가 높은 오른쪽 즉 road[x][y+1]의 값이 1인지 0인지를 판별해서 오른쪽으로 갈지 왼쪽으로 갈지를 미리 정하고나서 x를 +1해줄지 y를 +1해줄지를 나누면 될듯하다.

그리고 if 문을 통해서 y+1도 x+1도 다 1로 되어있다면 길이 막힌것으로 알고 break를 해주면된다.

이제 생각한 대로 코딩을 짜나가면 된다.

참고로 숫자는 input().split()을 통해서 넣었으므로 str형태라는 것에 유의하자!

 

x = 1
y = 1
while True:
    if road[x][y] == '2':
        road[x][y] = '9'
        break
    elif road[x][y] == '0':
        road[x][y] = '9'
    if road[x][y+1] != '1':
        y += 1
    elif road[x+1][y] != '1':
        x += 1
    else:
        break

 

문제에 보면 개미집의 시작은 2,2라고 명시되어 있다.

우리는 배열이 0부터 시작함으로 1,1에서 시작시켜주면 된다.

그 후 if문의 조건의 순서에 유의하며 조건문을 작성하면된다.

조건문을 작성할때는 무엇이 우선순위가 높은지를 생각하며 순서를 적어줘야한다.

현재 값은 0 혹은 2가 들어오게된다.

사실 이부분은 우선순위는 없다.

단지 2가 들어오면 9로 바꾸고 break를 해야한다는 점만 다를뿐이다.

 

그후 다음 데이터를 보고 x,y값의 증가를 선택해야하는 다음 if문을 보면

오른쪽에 우선순위가 있기때문에 y+1을 우선적으로 탐색해야한다.

그리고 y+1에도 1 x+1도 1이면 자동으로 else문이 실행되기 때문에 모든 벽이 1일 경우는 생략하고 그냥 break로 마무리해주었다.

 

이렇게 해서 출력하면 풀이가 완성된다.