배극곰의 IT식량창고

문제링크

https://www.acmicpc.net/problem/13414

문제설명

문제

국민대학교에서는 매 학기 시작 전 종합정보시스템에서 수강신청을 한다. 매 수강신청마다 아주 많은 학생들이 몰려 서버에 많은 부하가 가기 때문에, 국민대학교에서는 수강신청 부하 관리 시스템을 도입하기로 결정하였다. 새로운 관리 시스템은 다음과 같은 방식으로 동작한다.

1. 수강신청 버튼이 활성화 된 후, 수강신청 버튼을 조금이라도 빨리 누른 학생이 대기목록에 먼저 들어간다.
2. 이미 대기열에 들어가 있는 상태에서 다시 수강신청 버튼을 누를 경우 대기목록의 맨 뒤로 밀려난다.
3. 잠시 후 수강신청 버튼이 비활성화 되면, 대기목록에서 가장 앞에 있는 학생부터 자동으로 수강신청이 완료되며, 수강 가능 인원이 꽉 찰 경우 나머지 대기목록은 무시하고 수강신청을 종료한다.

위의 표는 최대 수강 가능 인원이 3명인 알고리즘 수업에 대해 6명의 학생이 수강신청을 진행한 모습이다. 버튼이 비활성화 된 후, 먼저 규칙 1을 적용하여 클릭을 2번 이상 한 학생의 중복된 대기목록을 삭제한다. 중복된 목록을 제거한 후, 맨 앞에서부터 최대 수강 가능 인원인 3명을 선정한다. 표의 맨 오른쪽에는 그 최종결과를 나타낸 모습이다. 이와 같은 방법을 이용하여 최종적으로 수강신청에 성공한 인원을 출력하는 프로그램을 작성하시오.

3 8
20103324
20133221
20133221
20093778
20140101
01234567
20093778
20103325

20103324
20133221
20140101

문제풀이

수강신청 부하 관리 시스템
  - 중복된 경우 대기번호 밀려난다. => 이전꺼 지우고 다시 삽입하는 것으로 구현하자!
  - 가장 앞에 있는 학생부터 수강 가능인원만큼 출력.

  - 하지만, K(수강 가능인원)가 db의 데이터 수보다 클 수 있다.

     => 이런 경우에는 K번 반복하며 인덱스 접근했다가 인덱스에러를 만나게된다.. 내가 그랬다.

     => 출력할때 K가 딕셔너리(리스트로 변환된) 의 길이 보다 클 경우와 작을경우 나눠서 출력하기.

처음엔 이 핵심들을 가지고 해시맵을 활용해서 구현하였다.

하지만 시간초과가 나와 sys.stdin.readline()을 이용하였는데 출력형식이 잘못되었다고 떠서,

rstrip()을 깜빡했단걸 깨달았다.

다시 기억하자...

input()으로 입력 받을땐 괜찮으나,

sys.stdin.readline() 이용하여 입력 받을경우 개행문자도 같이 받는다는거

코드

# 수강신청 부하 관리 시스템
# - 중복된 경우 대기번호 밀려난다. => 이전꺼 지우고 다시 삽입하면 될듯?
# - 가장 앞에 있는 학생부터 수강 가능인원만큼 출력.
import sys

input = sys.stdin.readline
K, L = map(int, input().split())
db = {}

for _ in range(L):
    student = input().rstrip()

    # db에 학생데이터 없다면
    if student not in db:
        db[student] = 1
    # 있다면 (버튼을 한번 더 누른 것이므로 맨뒤로 밀려남)
    else:
        del db[student]
        db[student] = 1

dbArr = list(db)
if len(dbArr) < K:
    for item in dbArr:
        print(item)
else:
    for i in range(K):
        print(dbArr[i])

문제링크

https://www.acmicpc.net/problem/9375

문제설명

2
3
hat headgear
sunglasses eyewear
turban headgear
3
mask face
sunglasses face
makeup face

5
3

문제풀이

코드

T = int(input())

for _ in range(T):
    n = int(input())
    dict = {}
    
    for i in range(n):
        wear = list(input().split())
        # 기존에 있었다면 리스트에 추가
        if wear[1] in dict:
            dict[wear[1]].append(wear[0])
        # 없던 옷종류라면 리스트 생성하여 옷 삽입
        else:
            dict[wear[1]] = [wear[0]]
    
    # 알몸만 아니면 되므로
    # 1종류 이상은 착용해야 한다.
    # 3종류(a, b, c) 가 있다면 착용가능한 조합은
    # (a개수+1) * (b개수+1) * (c개수+1)
    cnt = 1
    for key in dict:
        # 각 키에 해당하는값(배열이므로)의 길이
        cnt *= (len(dict[key]) + 1)
    
    # 집합 {a, b, c}로 나올 수 있는 경우
    # 공집합, {a}, {b}, {c}, {a,b}, {b,c}, {c,a}, {a,b,c}
    # 즉, 아무옷도 입지않은 경우를 빼준다.
    print(cnt - 1)

문제링크

https://www.acmicpc.net/problem/1302

문제설명

5
top
top
top
top
kimtop

top

문제풀이

리트코드의 twoSum 문제에서 해시테이블로 푸는걸 보고

해시맵 풀이를 익혔던것 같다.

핵심

1. 파이썬의 딕셔너리를 활용해서 해시맵 구현.

2. 조건에 맞게 삽입, 삭제

★3. 조건에 맞게 정렬 및 조회

    sorted() 를 쓸지, 리스트.sort() 를 쓸지 상황에 따라 판단.

   여기서는 딕셔너리를 리스트로 변환해

   리스트 내장함수 .sort()를 사용해 보았다.   

코드

N = int(input())

dict = {}

for _ in range(N):
    book = input()
    if book not in dict:
        dict[book] = 1
    else:
        dict[book] += 1

dictArr = list(dict.items())

dictArr.sort(key=lambda x: (-x[1], x[0]))

print(dictArr[0][0])

문제링크

https://www.acmicpc.net/problem/7785

문제설명

4
Baha enter
Askar enter
Baha leave
Artem enter

Askar
Artem

문제풀이

해시테이블로 쉽게 풀 수있다.

하지만 sorted()의 인자로 들어갈 수 있는 혹은 설정할 수 있는 것들에 대한 공부가 미흡한 것 같다.

리스트.sort() 메서드랑 헷갈리기도 하고...

코드

import sys
input = sys.stdin.readline
N = int(input())
dict = {}
# enter 삽입 , leave 삭제로 해석해서 해시테이블 구현하자

# 입력값 받아서 딕셔너리 아이템 삽입, 삭제
for _ in range(N):
    item = list(input().split())
    
    if item[1] == 'enter':
        dict[item[0]] = 1
    elif item[1] == 'leave':
        del dict[item[0]]

dictArr = sorted(dict.keys(), reverse=True)

for person in dictArr:
    print(person)

문제링크

https://www.acmicpc.net/problem/2206

문제설명

6 4
0100
1110
1000
0000
0111
0000

15

문제풀이

목표지점까지 BFS를 통해 이동하면서 갈수 있는 최단거리를 구하는 게 목표다.

한칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸.

틀린풀이 (처음 시도한 생각)

0. 시작위치 큐에 삽입.

    deque([(0, 0, 0, 1)]) =>  즉 큐를 생성하면서 (x, y, crush, cnt)를 삽입한것이다.

    x, y는 시작좌표, crush는 벽을 부쉈는지 체킹하는 변수, cnt 는 출발지로부터의 거리값 갱신하는 변수.

1. 큐에서 현재좌표 뽑아내서 현재위치에서 갈 수 있는 다음위치를 계산 (상하좌우).

2. 다음위치에 있는 노드 방문가능한지 조건문 로직

    - 조건문은 1차적으로 인덱스 범위에 있는지, 그리고 방문하지 않은 노드인지 체크

    - 1차적으로 통과하면 노드가 (1) 길인 경우와 (2) 벽인 경우를 나누어 조건문 검사.

        - 길인 경우에 거리값 갱신 및 큐에 다음위치와 갱신한 거리값 삽입  => append((nx, ny, crush, cnt + 1))

        - 벽인 경우에,

               - 부순적이 없다면 큐에 (다음 위치, 거리값 갱신한 변수, 부쉈는지 여부 판별하는 변수) 삽입.

                  => append((nx, ny, crush + 1, cnt + 1))

이렇게 순조로울 거라고 생각했으나 18%에서 틀리고 말았다.

틀린 코드

import sys
from collections import deque

input = sys.stdin.readline
N, M = map(int, input().split())
# N 행 , M 열
graph = [[0 for _ in range(M)] for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = [[0 for _ in range(M)] for _ in range(N)]
cnt = 0
possible = False
answer = []

# 입력값 받아서 맵 채우기
for i in range(N):
    graph[i] = list(map(int, input().rstrip()))

def BFS(x, y):
    global cnt, possible
    queue = deque([(x, y, 0, 1)])

    while queue:
        curX, curY, crush, cnt = queue.popleft()

        # 목표 좌표에 도달했다면 서치 종료
        if curX == N-1 and curY == M-1:
            possible = True
            answer.append(cnt)

        for i in range(4):
            nx = curX + dx[i]
            ny = curY + dy[i]
      
            # 인덱스 범위에 있고, 방문하지 않은 노드인지 체크 
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
                # 노드가 0이면 방문
                if graph[nx][ny] == 0:
                    queue.append((nx, ny, crush, cnt + 1))
                    visited[nx][ny] = 1
                # 다음 이동할 좌표가 벽이라면
                else:    
                    # crush값이 0 이면(그전에 벽 부수지 않았다면)
                    if not crush:
                        queue.append((nx, ny, crush + 1, cnt + 1))
                        visited[nx][ny] = 1
                        
    return possible

if BFS(0, 0):
    print(min(answer))
else:
    print(-1)

올바른 풀이

도저히 모르겠어서 서치해보니 역시나 예외인 테케가 있었다.

노드를 방문했었던 것이,

기존에 벽을 부순적이 있는 상태에서 방문한건지, 

부순적이 없는 상태에서 방문한건지 알아야 할 필요가 있다.

즉, 무슨말이냐 현재위치까지 오면서 벽을 부쉈는지 여부에 따라 visited 저장을 다르게 해야한다.

visited리스트를 기존과 다르게 visited[check][nx][ny]로 바꾸어 구현하자.

코드

정답코드

import sys
from collections import deque

input = sys.stdin.readline
N, M = map(int, input().split())
# N 행 , M 열
graph = [[0 for _ in range(M)] for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visited = [[[0]*2 for _ in range(M)] for _ in range(N)]
possible = False
answer = []

# 입력값 받아서 맵 채우기
for i in range(N):
    graph[i] = list(map(int, input().rstrip()))

def BFS(x, y):
    global possible
    queue = deque([(x, y, 0, 1)])

    while queue:
        curX, curY, crush, cnt = queue.popleft()

        # 목표 좌표에 도달했다면 서치 종료
        if curX == N-1 and curY == M-1:
            possible = True
            answer.append(cnt)

        for i in range(4):
            nx = curX + dx[i]
            ny = curY + dy[i]

            # 인덱스 범위 체크 
            if 0 <= nx < N and 0 <= ny < M:
                # 방문안한 노드라면 
                if not visited[nx][ny][crush]:
                    visited[nx][ny][crush] = 1
                    # 다음 이동할 노드가 길이라면
                    if graph[nx][ny] == 0:
                        queue.append((nx, ny, crush, cnt + 1))
                    # 다음 이동할 좌표가 벽이라면
                    else:
                        # 벽인데 그전에 다른벽을 부순적이 없다면
                        if not crush:
                            queue.append((nx, ny, crush + 1, cnt + 1))
                        
            # 벽인지 길인지 체크가 먼저냐
            # 아님 방문여부, 인덱스범위 체킹이 먼저냐 생각해보기

            # 일단 인덱스범위는 1차적으로 체킹해야될듯
            # => 잘못된 범위 참조해서 인덱스 오류날 수 있음
    return possible

if BFS(0, 0):
    print(min(answer))
else:
    print(-1)

문제링크

https://leetcode.com/problems/two-sum/description/

문제설명

num배열과 target이 주어지고

num배열 안에 있는 정수 중 두개의 합이 target이 되는 두 정수값의 인덱스를 출력하라고 한다.

문제풀이

브루트 포스를 활용하여 O(N^2) 시간복잡도로 풀수도 있지만

나는 투포인터를 사용하여 O(N)만에 풀었다. 정렬도 사용했으니 최종코드의 시간복잡도는 O(NlongN) 이겠다.

그리고 solution에는 해시테이블을 사용하여 푼 풀이도 있었다.

투포인터로 코드 구현할때

인덱스와 값을 묶어 튜플로 저장하는 과정에서 나는 직접 반복문을 돌려 추가하였다.

# for i in range(N):
    # arr.append((nums[i], i))  #(2, 0), (7, 1), (11, 2), (15, 3)

코드

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        N = len(nums)
        i, j = 0, N-1

        copyNums = sorted(enumerate(nums), key = lambda x: x[1])
        
        while i < j:
            sumValue = copyNums[i][1] + copyNums[j][1]
            if sumValue < target:
                i += 1
            elif sumValue > target:
                j -= 1
            else:
                return [copyNums[i][0], copyNums[j][0]]

문제링크

https://www.acmicpc.net/problem/1686

문제설명

3 1
0.000 0.000
500.000 0.000
179.000 0.000
358.000 0.000

Yes, visiting 2 other holes.

문제풀이

어려웠다.

평면에서 두점 사이 거리 공식으로 조건 검사 하는 것 까지는 인지하였으나,

처음에 입력될 벙커 개수를 알려주지 않아, EOF 에러 처리 하는 것을 구현했다.

핵심은 BFS를 활용하는 거다.

BFS시,

노드 방문 조건문에 방문체킹하는 로직 구현 안해서 메모리 초과 나기도 했으므로 꼭 체킹하자.

핵심

1. v * m * 60 이상 이동하면 안됨.(조건문 처리) 벙커를 통과하면서 가는 것을 구현

2. 벙커좌표 따로 리스트에 담아두기. BFS시 전부 탐색해야하므로 bunker 리스트 전체 돌려서 조건문 검사할것

   cf. 조건문: 방문 여부 / 범위내로 이동가능한지

3. 방문체크하는 배열 따로 만들어서 방문처리하고 조건문에도 방문여부 체킹.

코드

import math
from collections import deque

v, m = map(float, input().split())
xs, ys = map(float, input().split())
xt, yt = map(float, input().split())
bunker = []
cnt = 0 
maxRange = v * m * 60
result = False
visited = []

# 벙커 개수 안알려주는듯?
# EOF Error 잡기
while True:
    try:
        data = input()
        if not data:
            break
        x, y = map(float, data.split())
        bunker.append((x, y))    
    except:
        break
    

def calculateDist(a, b, x, y):
    return math.sqrt((x-a)**2 + (y-b)**2)

def BFS(xs, ys):
    global cnt, result
    queue = deque([(xs, ys, cnt)])
  
    while queue:
        curX, curY, cnt = queue.popleft()

        if calculateDist(curX, curY, xt, yt) < maxRange:
            result = True
            return result

        for item in bunker:
            xm, ym = item
            if item not in visited and calculateDist(curX, curY, xm, ym) < maxRange:
                queue.append((xm, ym, cnt+1))
                visited.append(item)

    return result

if BFS(xs, ys):
    print(f"Yes, visiting {cnt} other holes.")
else:
    print('No.')


# 이동하는 거리 구하기 (x, y) (a, b) 
# 평면에서의 두 점 사이 거리 = (a-x)**2 + (b-y)**2 

# 3 m/s 속도인데 제한시간 60s 안이면
# 179m 이상 갈 수 없다.

문제링크

https://www.acmicpc.net/problem/1806

문제설명

10 15
5 1 3 5 10 7 4 9 2 8

2

문제풀이

문제를 제대로 읽지 않아 여러번 틀린 문제이다.

첫번째로는 문제를 잘못 생각하여 리스트를 정렬해버려 문제가 발생하였다

두번째로 시간복잡도 생각이 미흡했고,

세번째로 문제 지문 똑바로 읽도록 해야겠다...

처음 시도한 코드는 아래와 같다

잘못된 코드

import sys

input = sys.stdin.readline
N, S = map(int, input().split())
arr = list(map(int, input().split()))

arr.sort()

i = 0
j = 0
minValue = 10 ** 5

while j < N:
    if sum(arr[i:j+1]) < S:
        j += 1
    elif sum(arr[i:j+1]) > S:
        i += 1
    else:
        minValue = min(j-i+1, minValue)
        i += 1
        j += 1

print(minValue)

문제를 잘못 읽었기도 하였지만,

위와 같이 구현하면, 매 반복시 갱신된 i, j값으로 리스트 슬라이싱 후 합을 구해버리게 된다.

따라서 시간복잡도가 O(N^2)이 되어 시간초과 날것은 자명한 셈

코드

올바른 코드

import sys

input = sys.stdin.readline
N, S = map(int, input().split())
arr = list(map(int, input().split()))

i = 0
j = 0
minValue = 10 ** 5
total = arr[i]

# 투 포인터로 배열탐색 (최대 N번) 
while j < N:
    if total < S:
        j += 1
        if j >= N:
            break
        total += arr[j]

    elif total >= S:
        minValue = min(j-i+1, minValue)
        total -= arr[i]
        i += 1

if minValue == 10**5:
    print(0)
else:
    print(minValue)

문제링크

https://www.acmicpc.net/problem/2230

문제설명

3 3
1
5
3

4

문제풀이

투포인터 알고리즘

주어진 배열이 정렬된 상태여야 효율적이다.

시간복잡도는 최악의 경우에도 O(N)

두 개의 포인터가 항상 left <= right 인 상태로 돌기 때문에 두 포인터가 증가하는 연산은 최대로 잡아도 N번만 수행된다.

핵심

1. 배열 오름차순 정렬 (내장함수 sort() 이용가능)

2. 두 포인터 이동 조건문 생각하기

    두 개의 수를 비교하는데 두 수의 차이가 M보다만 크다면 그것보다 큰 차이가 나는 두 수는 안봐도 된다.

   => 이말이 무슨 말이냐?

        A = [1, 2, 5, 6, 10] 이 있고 M=3 이라 할때 , 일단 두개 포인터를 i = 0, j = 1으로 두자.

        (1) arr[1] - arr[0] = 1 < M 이므로 우측포인터 i 1증가

        (2) arr[2] - arr[0] = 4 >= M 이다. 

             조건문 통과했으므로 어짜피 우리는 통과한 값중 가장 작은 값을 구할 것이므로

             이제 j만 증가시키는 일은 없다. (오름차순 정렬된 상태이므로)

             -  i 만 증가하거나

             - 두 개의 포인터가 인접한 상태라면 i, j 둘다 증가 

정리

두 수의 차이 < M:

  => 우측 포인터 이동  (조건 미충족이므로)

두 수의 차이 >= M:

  => 포인터가 바로 연속된 위치에 있다면

          -> 좌측, 우측 포인터 이동

       포인터 차이가 2이상 이면

          -> 좌측 포인터만 이동

코드

import sys

input = sys.stdin.readline
N, M = map(int, input().split())
A = [0] * N

for i in range(N):
    A[i] = int(input())

A.sort()

i = 0
j = 1
cnt = 0
answer = []

# 투포인터 활용
while j < N:
    if A[j] - A[i] >= M:
        answer.append(A[j]-A[i])
        i += 1
        j += 1
        if j - i > 1:
            j -= 1
    # 차이가 M보다 작다면
    else:
        j += 1
    
print(min(answer))

# 차이가 M이상
# M이상인 것들 중 차이가 가장 작은 거 고르면됨.

문제설명

현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 X 1 크기의 정사각형으로 이뤄진 N X M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.

맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해 놓은 매뉴얼은 이러하다.

현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다.

캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 횐전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다.

만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 방향이 바다인 칸이라 뒤로 갈 수 없는 경우에는 움직임을 멈춘다.

현민이는 위 과정을 반복적으로 수행하면서 캐릭터의 움직임에 이상이 있는지 테스트하려고 한다. 메뉴얼에 따라 캐릭터를 이동시킨 뒤에, 캐릭터가 방문한 칸의 수를 출력하는 프로그램을 만드시오.

입력

첫째 줄에 맵의 세로 크기 N과 가로 크기 M을 공백으로 구분하여 입력한다.

(3 <= N, M <= 50)

둘째 줄에 게임 캐릭터가 있는 칸의 좌표 (A, B)와 바라보는 방햔 d가 각각 서로 공백으로 구분하여 주어진다. 방향 d의 값으로는 다음과 같이 4가지가 존재한다.

0 : 북쪽

1 : 동쪽

2 : 남쪽

3 : 서쪽

셋째 줄부터 맵이 육지인지 바다인지에 대한 정보가 주어진다. N개의 줄에 맵의 상태가 북쪽부터 남쪽 순서대로, 각 줄의 데이터는 서쪽부터 동쪽 순서대로 주어진다. 맵의 외각은 항상 바다로 되어 있다.

0 : 육지

1 : 바다

처음에 게임 캐릭터가 위치한 칸의 상태는 항상 육지이다.

출력

첫째 줄에 이동을 마친 후 캐릭터가 방문한 칸의 수를 출력한다.

입력 예시

4 4

1 1 0 // (1, 1)에 북쪽(0)을 바라보고 서 있는 캐릭터

1 1 1 1

1 0 0 1

1 1 0 1

1 1 1 1

출력 예시

3

문제풀이

별도의 알고리즘 없이 조건 잘보고 그대로 구현만 하면 된다

핵심

1. 다음 이동할 좌표를 새로운 변수에 두고, (1) 검증하는 로직과 (2) 이동하는 로직 따로 생각하기

2. rCnt(회전횟수를 세는 변수) 만들어서(네방향 모두 체크하는 것이 조건이므로) 적절하게 초기화로직, 증가 로직 배치하기

코드

N, M = map(int, input().split())
visited = [[0 for _ in range(M)] for _ in range(N)]
arr = [[0 for _ in range(M)] for _ in range(N)]
x, y, direct = map(int, input().split())
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
answer = 1
rCnt = 0

for i in range(N):
    arr[i] = list(map(int, input().split()))

def rotateToLeft():
    global direct
    if direct == 0:
        direct = 3
    else:
        direct -= 1

# 현재위치 방문
visited[x][y] = 1

# 반복
while True:
    # [1번조건] 왼쪽으로 회전 로직
    rotateToLeft()
    
    # 다음 이동할 좌표 (회전이 끝난 상태의 방향에서 이동) 
    nx = x + dx[direct]
    ny = y + dy[direct]

    # [2번 조건]
    # 다음 좌표가 범위내에 있고, 육지이며, 방문하지 않았다면
    if 0 < nx <= M and 0 < ny <= N and arr[nx][ny] == 0 and not visited[nx][ny]:
        # 이동 (현재좌표 갱신)
        x, y = nx, ny
        visited[nx][ny] = 1
        answer += 1
        rCnt = 0
    else:
        rCnt += 1
    
    # [3번 조건] 4방향 모두 가본 칸이거나, 바다로 되어있다면 뒤로 한칸 이동
    if rCnt == 4:
        nx = x - dx[direct]
        ny = y - dy[direct]
        # [3번 예외조건] 뒤쪽이 바다라면 이동안하고 멈춤 (반복종료)
        if arr[nx][ny] == 1:
            break
        x, y = nx, ny
        rCnt = 0

print(answer)