[코드업 1099번] 성실한 개미

 

# 문제

영일이는 생명과학에 관심이 생겨 왕개미를 연구하고 있었다.

왕개미를 유심히 살펴보던 중 특별히 성실해 보이는 개미가 있었는데,
그 개미는 개미굴에서 나와 먹이까지 가장 빠른 길로 이동하는 것이었다.

개미는 오른쪽으로 움직이다가 벽을 만나면 아래쪽으로 움직여 가장 빠른 길로 움직였다.
(오른쪽에 길이 나타나면 다시 오른쪽으로 움직인다.)

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

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

미로 상자의 구조가 0(갈 수 있는 곳), 1(벽 또는 장애물)로 주어지고,
먹이가 2로 주어질 때, 성실한 개미의 이동 경로를 예상해보자.

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

미로 상자의 테두리는 모두 벽으로 되어 있으며,
개미집은 반드시 (2, 2)에 존재하기 때문에 개미는 (2, 2)에서 출발한다. 

 

입력

 

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

 

 

출력

 

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

 

입력 예시

1 1 1 1 1 1 1 1 1 1
1 0 0 1 0 0 0 0 0 1
1 0 0 1 1 1 0 0 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 1 0 1 0 1
1 0 0 0 0 1 2 1 0 1
1 0 0 0 0 1 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

 

출력 예시

1 1 1 1 1 1 1 1 1 1
1 9 9 1 0 0 0 0 0 1
1 0 9 1 1 1 0 0 0 1
1 0 9 9 9 9 9 1 0 1
1 0 0 0 0 0 9 1 0 1
1 0 0 0 0 1 9 1 0 1
1 0 0 0 0 1 9 1 0 1
1 0 0 0 0 1 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

 

---

 

My Solution

# 미로를 2차원 리스트로 받는다.
maze = [list(map(int, input().split())) for _ in range(10)]

if maze[1][1] == 2: # 처음 서 있던 자리에 먹이가 있는 경우
    maze[1][1] = 9
else:    
    # 개미의 첫 위치 초기화
    x, y = 1, 1
    flag = 0
    maze[1][1] = 9

    while True: # 2. 현 위치에서 아래쪽을 향할 때
        while True: # 1. 현 위치에서 오른쪽을 향할 때
            if maze[x][y+1] == 1: # 오른쪽에 벽이 있을 경우
                break
            elif maze[x][y+1] == 2: # 오른쪽에 먹이가 있을 경우
                y += 1
                maze[x][y] = 9
                flag = 1
                break
            else: # 오른쪽에 0이 있을 경우
                y += 1
                maze[x][y] = 9
        if flag == 1: # 오른쪽으로 이동해서 먹이를 얻었을 때, 루프를 완전히 탈출한다.
            break
        else:        
            if maze[x+1][y] == 1: # 아래쪽에 벽이 있을 경우
                break
            elif maze[x+1][y] == 2: # 아래쪽에 먹이가 있을 경우
                x += 1
                maze[x][y] = 9
                break
            else: # 아래쪽에 0이 있을 경우
                x += 1
                maze[x][y] = 9

# 개미 경로 출력
for i in range(10):
    for j in range(10):
        print(maze[i][j], end=' ')
    print()

 

Codeup Solution

m=[]
for i in range(12) :
    m.append([])
    for j in range(12) :
        m[i].append(0)

for i in range(10) :
    a=input().split()
    for j in range(10) :
        m[i+1][j+1]=int(a[j])

x=2
y=2
while True :
    if m[x][y]==0 :
        m[x][y]=9
    elif m[x][y]==2 :
        m[x][y]=9
        break

    if (m[x][y+1]==1 and m[x+1][y]==1) or (x==9 and y==9) :
        break

    if m[x][y+1]!=1 :
        y+=1
    elif m[x+1][y]!=1 :
        x+=1
    

for i in range(1, 11) :
    for j in range(1, 11) :
        print(m[i][j], end=' ')
    print()

 

주목할 부분

 

코드업 답안은 개미 이동 알고리즘을 하나의 루프로 해결한 것에 비해, 나의 답안은 이중루프인데다 코드의 depth가 너무 깊다. 처음 경우의 수를 조금 더 효율적으로 나눴다면 코드가 더 심플했을 것 같다.