마쏘's 개발 성장기

1. queue란?
- C++ 표준 라이브러리(Standard Template Library)에 있는 컨테이너(container)가 아니고,
- 특정 컨테이너 클래스(deque, list)의 캡슐화된 개체를 기본 컨테이너로 사용하는 클래스이며,

- container adapter로 구현된다고 한다.

2. queue의 특징

[벡터 원소 및 크기] & [벡터 원소 삽입 및 삭제]

- front(), back(): 제일 앞에 위치한 원소, 제일 뒤에 위치한 원소

- push(n), pop(): queue 뒤에 원소 n 삽입, queue 뒤에 원소 삭제

[벡터의 순회 및 출력]

- queue 자체는 iterator를 필요로 하지 않는다.

1. Vector란?
- C++ 표준 라이브러리(Standard Template Library)에 있는 컨테이너(container)로,
- 사용자가 쉽게 사용할 수 있도록 사전에 정의된 class이다.

2. Vector의 특징

[벡터 원소 및 크기] 

- front(), back(): 첫 번째 원소, 마지막 원소
- size(), capacity(): 원소의 개수 <-> 원소가 할당된 공간 크기
- begin(), end(): 첫 번째 위치, 마지막의 다음 위치

[벡터 원소 삽입 및 삭제]

- push_back(n): 마지막 위치에 n추가
- pop_back(): 마지막 원소 제거

- insert(pos, cnt, n): 위치 pos에 cnt 개의 n을 추가
- insert(pos, n): pos에 숫자 n을 추가

- erase(pos): pos에 있는 값을 제거

- erase(pos_start, pos_end): pos_start ~ (pos_end-1)까지 값들을 제거

[벡터의 순회 및 출력]

- vector에 index로 접근
- iterator 사용(직접 선언 or auto 문법 사용)

문제를 잘 이해해야 한다.

우선 내구도가 떨어지는 경우는 두 가지다.
1) 로봇이 어떤 칸으로 올라갈 때, 올라가려는 칸의 내구도가 감소한다.

2) 로봇이 어떤 칸으로 이동할 때, 이동하려는 칸의 내구도가 감소한다.

로봇을 옮기는 과정은 다음과 같다1) 벨트가 회전한다 rotate()2) 가장 먼저 올라와있던 로봇부터(가장 먼저 올라온 로봇이 아님) 벨트가 회전하는 방향으로 한 칸 이동한다. move()    이때 이동하기 위해서는 이동하려는 칸에 로봇이 없고, 내구도 >= 13) 올라가는 위치(컨베이어 벨트의 처음)에 로봇이 없으면 로봇을 올린다 put_robot()4) 내구도가 0인 칸의 개수가 k개 이상이라면 과정을 종료한다. 그렇지 않다면 1)번으로 돌아간다.

// 20055 컨베이어 벨트 위의 로봇
// https://www.acmicpc.net/problem/20055

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif

# include <stdio.h>
# include <iostream>
# include <deque>
using namespace std;

int n = 0, k = 0, step = 0, cnt = 0;
deque <int> belt;
deque<bool> robot;

void rotation() {
	belt.push_front(belt.back());
	belt.pop_back();

	robot.push_front(robot.back());
	robot.pop_back();
}

void move() {
	for (int i = n-2; i >= 0; i--){
		if(robot[i] && !robot[i+1] && belt[i+1] >= 1){
			robot[i] = false;
			robot[i+1] = true;
			belt[i + 1]--;
		}
	}
}

void put_robot() {
	if(belt[0]>0) {
		belt[0]--;		robot[0]=true;
	}	
}

int get_zero_cnt(){
	int zero = 0;
	for (int i = 0; i < 2*n; i++){
		if(belt[i]==0)
			zero++;
	}
	return zero;
}

int main(void){
	cin >> n >> k;

	for (int i = 0; i < 2 * n; i++){
		int val;
		cin >> val;
		belt.push_back(val);
		robot.push_back(false);
	}
	while(true){
		step += 1;
		rotation();
		robot[n - 1] = false;
		move();
		robot[n - 1] = false;
		put_robot();
		if(get_zero_cnt() >= k){
			cout << step << "\n";
			return 0;
		}
	}
	return 0;
}

원래는 que를 사용했는데 먼저 올라와 있던 로봇을 먼저 옮겨야 하는 걸 알게 되고나서 deque로 변경하였다.

참고한 블로그가 있는데 너무 설명이 잘 되어있어서 감사하게 공부했다!

deque 아이디어만 얻고 혼자 짜보고 확인했는데 나름 내 코드로 체화된 것 같아서 기쁘다!!

ssinee.tistory.com/entry/%EB%B0%B1%EC%A4%80-20055%EB%B2%88-%EC%BB%A8%EB%B2%A0%EC%9D%B4%EC%96%B4-%EB%B2%A8%ED%8A%B8-%EC%9C%84%EC%9D%98-%EB%A1%9C%EB%B4%87-%EC%82%BC%EC%84%B1-%EA%B8%B0%EC%B6%9C

보통 알고리즘을 작성할 때, 연산 속도와 메모리 공간을 최대한 활용할 수 있도록 효울적으로 작성하는데,

어떤 문제는 메모리 공간을 약간 더 사용하면 연산속도를 비약적으로 증가시킬 수 있는 방법이 있다.

그 방법 중 대표적인 방법이 다이나믹 프로그래밍 기법이다.

[ 다이나믹 프로그래밍을 사용할 수 있는 조건 ]
     1. 큰 문제를 작은 문제로 나눌 수 있다.

     2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

다이나믹 프로그래밍을 코드로 구현하기 위해서는 메모이제이션 기법을 사용하는데,
그저 다이나믹 프로그래밍 구현 방법 중 하나라고 생각하면 된다.

메모이제이션 기법은 한 번 구한 결과를 메모리 공간에 저장해두고 같은 식을 다시 호출하면

메모한 결과를 그대로 가져오는 기법을 의미한다.

(보통 메모리 공간은 dictionary나 list를 사용하는 것 같다)

1. 1로 만들기

나의 생각)
가능한 연산은 2,3,5로 나누는 것과 1로 빼는 것이다.

메모리에 저장할 값은 정수 i에서 1 ~ i까지의 연산 최소 횟수로 정의하였다.

값을 계산하기 위해 arr[0] = 0; arr[1] = 0; arr[2] = 1; arr[3] = 1; arr[4] = 2; arr[5] = 1를 미리 초기값으로 지정하였다.

''' 
input 1:[26]
output: 3 
input 2: [20730, 16465, 27368, 21803, 29081, 23215, 16419, 12244, 16602, 25045]
output 2: 10 13 11 13 14 13 11 11 11 10
input 3: [20730, 16465, 27368, 21803, 29081, 23215, 16419, 12244, 16602, 25045]
output 3: 8 10 9 9 11 11 11 8 11 10 
'''
nums = [8000, 6814, 2553, 3918, 7034, 5806, 5471, 3012, 6986, 5347]

def make_to_one(n):
    arr = [0 for _ in range(n+1)]
    arr[0] = 0; arr[1] = 0; arr[2] = 1; arr[3] = 1; arr[4] = 2; arr[5] = 1

    if n <= 5: 
        print(arr[n])

    operaters = [1,2,3,5]
    for a in range(6, n+1):
        candidates = [30000,30000,30000,30000]
        candidates[0] = arr[a-1] + 1
        if a % 2 == 0:
            candidates[1] = arr[int(a/2)] + 1
        if a % 3 == 0:
            candidates[2] = arr[int(a/3)] + 1
        if a % 5 == 0:  
            candidates[3] = arr[int(a/5)] + 1
        arr[a] = min(candidates)

    print(arr[n], end = ' ')

for num in nums:
    make_to_one(num)

2. 개미 전사

주어진 배열에서 한 칸 이상 띄워서 더했을 때 나올 수 있는 최댓값을 구해야 하는 문제이며,

메모리에 저장할 값은 해당 i번째까지 구할 수 있는 최댓값으로 정의하였다.

최댓값을 구할 때 나올 수 있는 경우의 수는

     1) 더하지 않을 때: i-1번째에 저장된 값을 저장

     2) 더할 때: i-2번째에 저장된 값에 현재 i값을 더한 값을 저장

따라서 i에 저장할 최댓값은 위 경우의 1), 2) 값을 비교하여 나오는 최댓값을 구해서 대입하면 된다.

# n = int(input())
# storage = list(map(int, input().split()))
# print(n, storage)

'''
input 1: 4, [1,3,1,5]
output 1: 8

input 2: 10, [11, 6, 12, 3, 4, 1, 18, 2, 17, 16]
output 2: 62
'''

n, storage = 15, [1, 100, 1, 1, 1, 100, 1, 100, 100, 1, 1, 100, 100, 100, 1]
table_DP = [0 for _ in range(n)]

table_DP[0] = storage[0];
table_DP[1] = max(storage[0], storage[1])

for i in range(2,n):
    candidates = []
    # defore max sum
    candidates.append(table_DP[i-1])
    # front + my sum
    candidates.append(table_DP[i-2] + storage[i])
    table_DP[i] = max(candidates)

print(table_DP[n-1])

3. 바닥 공사

숫자에서 뿐만 아니라 도형적인 패턴에서도 큰 문제를 작은 문제로 쪼갤 수 있는지를 판단하기 위한 문제라고 생각한다.

메모리에 저장할 값을 가로가 i일 때, 바닥을 채울 수 있는 모든 경우의 수로 정의하였다.

그러나, [i-1]과 [i]와의 관계성을 구하는데 2x1의 덮개에서 중복이 발생해 이를 해결해야 했다.

이를 해결하기 위해서는 [i-1]와 [i-2]와 [i]의 관계를 살펴보아야 하는데,

1) [i-1]에서 [i]까지는 2x1만 채울 수 있다.

2) [i-2]에서 [i]까지는 2x1과 1x2와 2x2가 다 채워질 수 있는데,

                              여기서 2x1은 1)의 경우에서 채울 수 있으므로 

총 우리가 고려해야 하는 것은  [i-1]에서 2x1로 채울 때, [i-2]에서 1x2 또는 2x2로 채울 때만 고려하면 된다.

!) 아 참, 큰 수로 나누는 이유는 모든 경우의 수는 값이 커지므로 출력 범위를 줄이기 위함이라고 한다.

#n = int(input())
n = 345
div_num = 796796

'''
input:  [760,    765,    378,    345,    4,  521,    741,    640,    464,    530] # n이 들어있는 배열
output: [536911, 448425, 551139, 336313, 11, 373121, 481185, 496871, 646635, 603879] # n에 해당하는 answer가 들어있는 배열
'''

table = [0 for _ in range(1001)] # 1 <= n <= 1000, table = [0] * 1001
table[1], table[2] = 1, 3

for i in range(3, n + 1):
    table[i] = table[i-1] + 2 * table[i-2]

print(table[n] % div_num)

4. 효율적인 화폐 구성

이부분을 풀면서 그리디와 DP를 구분해보았는데 여기서 중요한 건 "정당성"이다. 그리디에서는 화폐의 단위가 배수로 커졌기 때문에 큰 수부터 나누는 것이 맞으나, 화폐 단위끼리 간격이 달라진다면 무조건 큰 화폐로 채우는 것이 최선이 아닐 수 있다.

예를 들면 화폐 종류가 3개로 1, 7, 11 이렇게 있다고 하자. 우리가 구해야하는 화폐의 금액은 115원이다.

그리디 방식으로 풀게 된다면, '11' 10개, '1' 5개로 총 15개가 필요하다.

그러나, 11+7=18로 115는 18*6 + 7이므로 따라서 '11' 6개 '7' 7개로 총 13개가 필요하다.이로써 화폐 단위가 다를 때 큰 수부터 나누어 구하는 것이 최선의 값을 보장하지 못한다.

다시 DP로 돌아오자면, 메모리에 저장할 값은 화폐로 저장할 수 있는 최소 개수로 정의하였다.화폐 종류가 2 하나라면,a) 2부터 n까지 2로 만들 수 있는 i번째에 값을 갱신한다.

화폐 종류가 하나 이상이라면,b1) 화폐 선택  b2) a)를 반복하면 된다.

이때 갱신할 값은 현재 자신에 채워진 개수 & 자신이 가진 돈에서 화폐 단위만큼 뺐을 때 최소 개수 + 1을 비교해서 작은 값으로 갱신하면 된다.

# n,m = map(int, input().split()) 
# coins = [0] * n
# table = [10001] * (m + 1) # 0 <= m <= 10000
# for i in range(n):
#     coins[i] = int(input());     table[coins[i]] = 1

# input 1 
n, m = 3, 115
coins = [1, 7, 11]
# ouput 1
14

'''
input 2
n, m = 10, 9668
coins = [50, 46, 80, 85, 66, 28, 95, 22, 99, 7] 
output 2
98
input 3
n, m = 10, 5726
coins = [92, 72, 97, 89, 29, 12, 80, 90, 81, 16]
output 3 
60
'''
table = [10001] * (m + 1) # 0 <= m <= 10000

for coin in coins:
    table[coin] = 1

for coin in coins:
    for step in range(coin, m+1):
            table[step] = min(table[step], table[step-coin] + 1)

if table[m] == 10001:
    print("-1")
else:
    print(table[m])

자세한 설명은 아래 포스트를 참고하기
masso.tistory.com/80?category=891816

1. 부품 찾기

: 다른 input 만드느라 애 좀 먹었다..ㅠㅜ

1-0. input & output

# input 1
N, M = 5, 3
store, client = [8, 3, 7, 9, 2], [5, 7, 9]
# ouput 1
# no yes yes

# input 2
N, M = 50, 20
store = [73,15,26,59,49,44,8,47,63,74,66,81,67,41,52,45,57,4,51,12,10,37,64,7,48,23,42,18,71,55,36,61,83,82,2,20,94,76,28,58,50,92,79,70,96,19,54,97,40,86]
client = [4,35,20,53,93,6,63,52,21,41,5,77,91,78,79,7,46,39,64,95]
# output 2
# yes no yes no no no yes yes no yes no no no no yes yes no no yes no

# input 3
N, M = 60, 60
store = [911,643,184,439,855,981,950,776,519,204,321,47,749,53,851,272,970,270,42,137,523,251,990,171,487,860,796,19,841,46,799,215,333,766,214,709,687,299,334,554,991,396,163,473,869,76,549,128,821,756,703,463,60,283,706,81,314,415,517,375]
client = [500,923,351,303,489,294,579,708,287,382,137,906,229,788,332,251,862,486,795,638,932,725,573,541,329,177,324,868,710,277,290,909,948,364,87,727,652,497,977,618,532,258,949,632,687,29,735,580,617,770,70,946,569,743,189,388,322,636,61,200]
# output 3
# no no no no no no no no no no yes no no no no yes no no no no no no no no no no no no no no no no no no no no no no no no no no no no yes no no no no no no no no no no no no no no no

1-1. 정렬한 후 이진 탐색 binary Search

'''=== way1. binary search ==='''
def binary_search(target, start, end, arr):
    if start > end:
        return False
    mid = (start + end) // 2 # 괄호가 없으면 우선 순위가 달라짐
    if arr[mid] == target:
        return True
    elif target < arr[mid]:
        return binary_search(target, start, mid-1, arr) # -1 자꾸 까먹음..!
    else:
        return binary_search(target, mid+1, end, arr) # +1 자꾸 까먹음..!

start_time = timeit.default_timer()
store = sorted(store)
for target in client:
    if binary_search(target, 0, N-1, store):
        print("yes", end = ' ')
    else: 
        print("no", end = ' ')
print()
end_time = timeit.default_timer()
print(">> binary_search time: ", end_time - start_time)

1-2. set의 성질 이용하기

'''=== way2. set() ==='''
# N = int(input())
# store = set(map(int, input().split())) #!! list 대신 set으로!
# M = int(input())
# client = list(map(int, input().split()))

set_store = set(store)
start_time = timeit.default_timer()
for target in client:
    if target in set_store:
        print("yes", end = ' ')
    else:
        print("no", end = ' ')
end_time = timeit.default_timer()

1-3. 계수 정렬(생략)

2. 떡볶이 떡 만들기

: 손님이 원하는 길이에 딱 맞는 최대 높이를 찾을 수 없다면,
  손님이 원하는 길이보다 더 많이 주는 높이 중에서 최댓값을 반환해야한다!! (아래 input 2,3 참고)

2-0. input

# input 1
# N, M = 4, 6
# rice_cakes = [19, 15, 10, 17]
# answer:15

# input 2
# N, M = 50, 456
# rice_cakes = [693, 124, 802, 928, 882, 939, 375, 944, 810, 860, 310, 110, 851, 433, 888, 957, 574, 320, 673, 389, 
# 594, 807, 809, 946, 949, 138, 688, 136, 581, 398, 649, 225, 188, 301, 743, 299, 623, 220, 643, 767, 588, 183, 551, 
# 264, 184, 547, 376, 766, 811, 162]
'''절단기에 설정할 수 있는 높이의 최댓값:  872
>> sequential_search time:  0.0007, >> recursive_binary_search time:  0.0003, >> while_binary_search time:  0.0003
'''

# input 3
N, M = 200, 1357
rice_cakes = [273, 20, 157, 49, 24, 224, 175, 193, 169, 153, 141, 297, 258, 287, 268, 154, 211, 185, 113, 294, 129, 117, 242, 91, 
122, 106, 215, 292, 271, 188, 56, 167, 256, 63, 172, 206, 213, 51, 249, 146, 54, 124, 97, 198, 264, 200, 197, 156, 209,
13, 252, 62, 152, 236, 27, 207, 160, 277, 10, 176, 241, 223, 46, 274, 205, 262, 22, 291, 293, 132, 11, 253, 41, 283, 
199, 110, 126, 36, 71, 105, 220, 87, 231, 31, 171, 128, 263, 270, 30, 95, 281, 183, 155, 260, 216, 135, 44, 257, 276, 
104, 254, 279, 217, 12, 299, 55, 149, 138, 58, 125, 246, 266, 66, 201, 75, 85, 57, 77, 229, 101, 133, 21, 35, 161, 240,
286, 131, 290, 99, 130, 88, 184, 261, 247, 83, 151, 84, 238, 81, 221, 267, 265, 89, 173, 123, 245, 79, 26, 102, 225, 
278, 219, 186, 144, 68, 166, 180, 120, 162, 118, 52, 25, 139, 45, 50, 43, 163, 17, 86, 255, 168, 140, 181, 28, 96, 53,
112, 233, 109, 70, 237, 196, 248, 80, 232, 159, 111, 100, 275, 194, 78, 251, 272, 295, 76, 94, 289, 174, 47, 202]
'''절단기에 설정할 수 있는 높이의 최댓값:  240
>> sequential_search time:  0.0011, >> recursive_binary_search time:  0.0005, >> while_binary_search time:  0.0006
'''
# answer = 240

2-1. 순차 탐색 sequential Search

'''sequential_search'''
def sequential_search(arr):
    max_H = max(arr)
    while max_H > 0:
        total = 0
        for ele in arr:
            if ele > max_H:
                total += ele - max_H
        if total >= M:
            print("절단기에 설정할 수 있는 높이의 최댓값: ", max_H)
            break;
        max_H -= 1
            
'''%% 입력의 범위가 최대 10억까지의 정수이므로 시간 초과를 받는다.'''  
start_time = timeit.default_timer()
sequential_search(rice_cakes)
end_time = timeit.default_timer()
print(">> sequential_search time: ", format(end_time - start_time, ".4f"))

2-2. 이진 탐색 binary Search

'''binary_search'''
def binary_search(ans, arr, minH, maxH):
    global result
    if minH > maxH:
        return -1
    midH = (minH + maxH) // 2
    total = 0
    for ele in arr:
        if ele > midH:
            total += ele - midH
    if total >= ans:
        result = midH
        return binary_search(ans, arr, midH+1, maxH)
    elif total < ans:
        return binary_search(ans, arr, minH, midH-1)

start_time = timeit.default_timer()
result = 0
binary_search(M, rice_cakes, 0, max(rice_cakes))
print("절단기에 설정할 수 있는 높이의 최댓값: ", result)
end_time = timeit.default_timer()
print(">> recursive_binary_search time: ", format(end_time - start_time, ".4f"))

1. 음료수 얼려먹기

: 단순하게 0인 부분을 채우고, 채워진 0 부분이 몇 개인지 출력하면 되는 문제이다.

'''
input:
4 5 
00110
00011
11111
00000
output: 3

input:
5 7
1010101
0101010
1111000
0100111
0110000
output: 8

input:
4 5
10001
00000
00000
10001
output: 1
'''

1) BFS

from collections import deque
dpos = [(0, 1), (-1, 0), (0, -1), (1, 0)]

def __main__():
    N, M = map(int, input().split())

    ice_tray = [0 for _ in range(N)]
    for i in range(N):
        ice_tray[i] = list(map(int, input()))
    
    ''' another way
    ice_tray = []
    for i in range(N):
        ice_tray.append(list(map(int, input())))
    '''

    visit = [[0 for col in range(M)] for row in range(N)]
    cnt = 0
    que = deque()

    for i in range(N):
        for j in range(M):
            if visit[i][j] or ice_tray[i][j]:
                continue
            que.append((i, j))
            visit[i][j]=1
            cnt += 1
            while que:
                x, y = que.popleft()
                for dx,dy in dpos:
                    nx, ny = x + dx, y + dy
                    if nx < 0 or nx >= N or ny < 0 or ny >= M or visit[nx][ny]:
                        continue
                    visit[nx][ny] = 1

                    if ice_tray[nx][ny] == 0:
                      que.append((nx,ny))

    return  print("output >>", cnt) 

__main__()

나의 실수> 우선 input에서 input().split()을 사용하면 배열에 제대로 채워지지 않는다. (이건 왜 안 되는지 모르겠다..)

2) DFS

dpos = [(0,1),(1,0),(0,-1),(-1,0)]

def DFS(x, y):
    global N, M, ice_tray, visit

    for dx, dy in dpos:
        nx, ny = x + dx, y + dy
        if nx < 0 or nx >= N or ny < 0 or ny >= M or visit[nx][ny] == 1:
            continue

        visit[nx][ny] = 1
        if ice_tray[nx][ny] == 0:
            DFS(nx, ny)

전역변수로 사용하기 위해서 global 키워드를 사용했다.

def __main__():
    global N, M, ice_tray, visit

    N, M = map(int, input().split())

    ice_tray = [0 for _ in range(N)]
    for row in range(N):
        ice_tray[row] = list(map(int, input()))

    visit = [[0 for _ in range(M)] for _ in range(N)]

    cnt = 0
    for i in range(N):
        for j in range(M):
            if ice_tray[i][j] == 1 or visit[i][j] == 1:
                continue
            visit[i][j] = 1
            DFS(i,j)
            cnt += 1
    print("output >> ", cnt)
    return 0

__main__()

2. 미로 탈출
: 미로에서 탈출 가능한 최단 경로의 길이를 출력하면 된다.

''' 
input:
5 6
101010
111111
000001
111111
111111
output: 10

input:
5 10 
1001100011
1001110100
1111010111
1010010101
1110111101
output: 20
'''

1) BFS

: BFS는 너비 우선 탐색이기 때문에 찾은 값이 최소 거리일 수 밖에 없다.

from collections import deque
dpos = [(0, 1), (-1, 0), (0, -1), (1, 0)]

def BFS(x,y,r):
  global N, M, maze, visit
  visit[x][y]=1
  que = deque()
  que.append((x,y,r))
  while que:
      x,y,r = que.popleft()
      for dx,dy in dpos:
        nx, ny, nr = x + dx,y + dy, r+1
        if nx < 0 or nx >= N or ny < 0 or ny >= M or visit[nx][ny]:
          continue
        if nx == N-1 and ny == M-1:
          return nr

        visit[nx][ny] = 1
        if maze[nx][ny] == 1:
          que.append((nx, ny, nr))

def __main__():
    global N, M, maze, visit

    N, M = map(int, input().split())
    maze = [0 for _ in range(N)]
    for i in range(N):
        maze[i] = list(map(int, input()))
    visit = [[0 for col in range(M)] for row in range(N)]

    return print("output >>", BFS(0, 0, 1))
  
__main__()

2) DFS

: DFS는 깊이 우선 탐색이므로 출구에 도착했을 때 계산한 경로들 중에 제일 작은 값을 찾아서 출력해야한다.

dpos = [(0, 1), (-1, 0), (0, -1), (1, 0)]

def DFS(x,y,cnt):
  global N, M, mincnt
  if x == N-1 and y == M-1:
    if mincnt > cnt:
      mincnt = cnt
    return cnt

  for dx, dy in dpos:
    nx, ny = x + dx, y + dy
    if nx < 0 or nx >= N or y < 0 or ny >= M or arr[nx][ny] == 0 or visit[nx][ny] == 1:
      continue
    
    if arr[nx][ny] == 1:
      visit[nx][ny] = 1
      DFS(nx, ny, cnt+1)
      visit[nx][ny] = 0

def __main__():
    global N, M, mincnt, arr, visit

    N, M = map(int, input().split())
    mincnt = 201 * 201
    arr = []
    for i in range(N):
        arr.append(list(map(int, input())))

    visit = [[0 for col in range(M)] for row in range(N)]
    visit[0][0] = 1

    DFS(0, 0, 1)

    return print("output >>", mincnt)
  
__main__()

BFS와 DFS로 문제를 풀면서 부족했던 점은 조건을 기입할 때 visit과 arr을 사용하는 것에 혼동하는 경우가 있는 것 같다.

주의해야 할 것 같다!

github.com/katherine4191/This-is-a-coding-test/tree/master/CH5%20BFS%26DFS