[Algorithm] 백준_1592번: 달팽이2

오늘의 문제는 🚀 백준 1592번: 달팽이2이다.

분명 브론즈..인데 왜 때문에 못풀겠지..? 내 실력 눈감아😂

테스트케이스 이해하기

입력으로 숫자가 주어지면 n * m 크기의 어레이를 꺽어가면서 돌때 몇번이 꺽이는지 찾는 것이다.

1차 시도 : 실패

이 시도는…마지막 한줄이 꺽이지 않고 쭉 이어질때 해결하지 못한다.. 허흑

• 알고리즘

1. 이차원 배열 모서리를 다 돈다.
2. 그 다음에 차례대로 안으로 돌아간다.
3. 방향이 바뀔 때 마다 count의 갯수를 올려준다.

• 문제점
  • 마지막에 한 줄이 쭈르륵 남아있을 경우 판단하지 못함.

2차 시도 : 성공

접근법이 떠오르지 않아 해당 부분만 인강을 수강했다….!

생각은 비슷했지만 훨씬 간단한 방법으로 활용해서 문제를 푸셨다.

mode 아이디어를 활용해서 나름의 방식을 풀렸더니 통과되었다!

• 알고리즘

1. dx, dy를 꺽이는 방향 순서대로 셋팅한다.

2. 모든 칸을 다 채울동안 while문을 돈다.

3. mode의 값을 더한 x,y가 범위안에 있다면 다음 칸이 0인지 확인한 후,

   ​ 0이 아니면, mode를 업데이트해주고, result 값을 추가 한다.

   ​ 그 후 x,y 값을 업데이트 하고 count 증가!

4. 범위 안에 없다면 mode를 업데이트해주고, result 값을 추가 한다.

정답코드

n,m = map(int, input().split())
arr = [[0]*m for _ in range(n)]
dx=[0,1,0,-1] #우, 하, 좌, 상
dy=[1,0,-1,0]

x = y = mode = count = result = 0
arr[0][0]=1


while count != n*m-1:
    if -1< x+dx[mode] <n and -1< y+dy[mode] <m:
        if arr[x+dx[mode]][y+dy[mode]] != 0:
            mode = (mode + 1) % 4
            result += 1

        x += dx[mode]
        y += dy[mode]
        arr[x][y] = 1
        count += 1

    else:
        mode = (mode+1)%4
        result +=1


print(result)

🚀Reference: 백준 1592번 - 달팽이2