수테크📱⌚️👀

문제🤔

NxN 크기의 미로에서 출발지에서 목적지에 도착하는 경로가 존재하는지 확인하는 프로그램을 작성하시오. 도착할 수 있으면 1, 아니면 0을 출력한다.

주어진 미로 밖으로는 나갈 수 없다.

다음은 5x5 미로의 예이다.
 

13101

10101

10101

10101

10021

마지막 줄의 2에서 출발해서 0인 통로를 따라 이동하면 맨 윗줄의 3에 도착할 수 있는지 확인하면 된다.

[입력]
 

첫 줄에 테스트 케이스 개수 T가 주어진다.  1<=T<=50
 

다음 줄부터 테스트 케이스의 별로 미로의 크기 N과 N개의 줄에 걸쳐 미로의 통로와 벽에 대한 정보가 주어진다. 0은 통로, 1은 벽, 2는 출발, 3은 도착이다. 5<=N<=100

[출력]
 

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 계산결과를 정수로 출력하거나 또는 ‘error’를 출력한다.

내 풀🦷

# 4875. 미로
# 출발지에서 목적지에 도착하는 경로가 존재하는지 확인
# 마지막 줄의 2에서 출발, 0인 통로를 따라 이동하면 맨 윗줄의 3에 도착하는지
# 사방 탐색
dx = [0, 1, 0, -1] # 범위 제대로 확인
dy = [-1, 0, 1, 0]
def miro(i, j):
    global result # 결과값 전역변수로 설정해주기
    visited[i][j] = True
    for k in range(4):
        di = i + dx[k]
        dj = j + dy[k] # 하나하나 신경써서 적기
        if 0 <= di < N and 0 <= dj < N and not visited[di][dj]:
            # 탐색안했고 0이면 재귀
            if arr[di][dj] == 0:
                miro(di, dj)
            # 3 도착하면 성공
            elif arr[di][dj] == 3:
                result = 1 # 결과값 성공으로 바꾸기
                break

T = int(input())
for tc in range(1, T + 1):
    N = int(input()) # 미로의 크기
    arr = [list(map(int, input().strip())) for _ in range(N)]
    # 방문 검사
    visited = [[False for _ in range(N)] for _ in range(N)]
    result = 0 # 결과값

    for i in range(N-1, -1, -1):
        for j in range(N-1, -1, -1):
            if arr[i][j] == 2:
                miro(i, j) # 함수에 시작점 넣어주기

    print(f'#{tc} {result}')

벽이 없는곳을 피해서 가야한다고라고라고라파덕 혼자 이러고 있다가..

뭔가 오늘 시험에서 사용한(?) 델타 + dfs에서 배운 개념들 + 재귀 다 쓰면 해결할 듯(?)으로 생각해보았습니다아 🤔

중간에 실수한 부분들 😵‍💫

- 델타 범위 (취중 코딩해서 그런가 잘못 적음;;;;

- dj = i + dk[k] (역시 잘못 적음....)

- 입력 받을 때 strip() 써주지 않아서 런타임에러 발생.... => 사실 아직도 잘 모르겠음 왜인지...

strip()은 공백을 제거하면 되는거자나요??

split()을 안 적어주면 된다 아닌가요??

아시는 멋진분의 댓글 기다리고 있겠습니다...

참고함면 좋을 개념들 ✍️

1) 델타를 이용한 2차 배열 탐색

: 2차 배열의 한 좌표에서 4방향의 인접 배열 요소를 탐색하는 방법(8방도 가능)

arr[0...N-1][0...N-1] # N * N 배열
di = [0, 1, 0, -1] # 하, 우, 상, 좌
dj = [1, 0, -1, 0]
for i in range(N):
	for j in range(N): # 여기까지는 우리가 흔히아는 이차원 배열
    	for k in range(4): # 델차를 이용
        	ni = i + di[k]
            nj = j + dj[k]
            if 0 <= ni < N and 0 <= nj < N: # 범위에 안에 들어있는 인덱스면...
            	f(arr[ni][nj]) # 이 점을 기준으로 더해주든 개수를 세주던 더 나아가던 무궁무진한 문제들이 나올 수 있다

2) 재귀를 활용한 dfs

: 재귀를 활용함으로써 쉽게 dfs를 구현할 수 있다(내용은 안쉬움... 이해하기 힘들었음..)

def dfs(v):
    global visited
    # print(v, "-", end='')
    visited[v] = True # 이거에 해당하면 진행
    # v 노드에서 갈 수 있는 노드를 확인 (인접한 노드)
    for u in graphs[v]:
        if visited[u] == True:  # 방문을 했다면
            continue
        # 방문을 하지 않았다면 방문을 진행
        else: # u가 visited안에 들어있지 않다면 u를 다시 dfs 해주면 된다
            dfs(u)  # 모든 요소가 다 돌아가서 모든 요소가 트루로 바뀌면 끝난다.

# 재귀함수로 부분집합 만들기
# bits: 해당 인덱스의 요소를 사용할지의 유무 (1은 사용하고 0은 아님)
# depth : 내가 얼마나 함수를 재귀호출했는지에 대한 카운트 값...
def recur(bits, depth):
    # 기저 조건
    if depth == N:
        for i in range(N):
            if bits[i] == 1:
                print(arr[i], end=' ')
        print()
        return

    for i in range(2): # 0, 1
        bits[depth] = i
        # 자기 자신을 호출
        recur(bits, depth + 1)


N = 4
arr = [1, 2, 3, 4]
recur([0] * N, 0)

# result
4 
3 
3 4 
2 
2 4 
2 3 
2 3 4 
1 
1 4 
1 3 
1 3 4 
1 2 
1 2 4 
1 2 3 
1 2 3 4

재귀함수 너무 어려워요오....제제제.....기.........랄,,,,

여기서 제일 중요한 포인트는 [0, 0, 0, 0] 배열을 끝까지 만들어주고 역으로 만들어져 나가는 느낌이라는거?

return을 받았을 때, 제일 처음이 아닌 자신을 호출했던 곳으로 돌아가 0이 아니라 1인 경우를 만들어준다는거??

그래서 답을 출력했을때, 리스트에 가장 먼저 저장된 1이 아니라 4가 나오는 부분이 정말 중요 포인트인거 같다...

오늘은 싸피에서 스택에 관해 배웠다

복습으로는 백준에 있는 스택 문제 풀기..

다 풀고 싶었는데 어제 풀다 만 브루투토스에 체스가 너무 오래 걸려서 2문제 남았다...

내일 해야지;;;;; 다음에 체스도 시간나면 적어보는걸로

서론이 너무 길었고 오늘 소개해 드릴 문제는 백준 9012. 괄호입니다!!!

오늘 swea에서도 비슷한 문제를 풀었는데 조금 쉬운 버전입니다 ^^

그럼 고 🌟🌟

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

NO
NO
YES
NO
YES
NO

# 9012. 괄호 - 오늘 나를 지겹게 한 ^^ : 오늘 학교에서 이거 비슷한 문제 한 2시간 머리 싸맸거덩요...
stack = [] 						# 괄호를 담을 리스트를 만들어 줬습니다
def gal(text): 					# 함수로 만드는게 조금 편해져서 만들었습니다
    for ch in text: 			# 텍스트 내부를 순회하면서
        if ch == '(': 			# 문자'('가 있으면
            stack.append(ch)	# 문자를 리스트에 추가해줍니다
        elif ch == ')':			# 문자')'가 있으면
            if len(stack) == 0: # 리스트의 길이를 확인해줘야 하는데 0이라면 열린기호가 없어서 틀린 text입니당
                return 'NO'		# 고로 NO를 반환해 줬어요
            else:				# 길이가 0이 아니라면...
                if stack[-1] == '(': 	# 스택의 마지막에 (가 있으면 
                    stack.pop()			# 마지막 (를 삭제하고
                    continue			# 계속해서 다음 문자를 확인해 줬습니다
                else:
                    return 'NO'			# 하지만 열린기호 '('가 아닌 다른게 들어있으면 틀린 문장이겠죠

    if len(stack) == 0: # 결론적으로 ')'가 나올떄 '('을 지웠으므로 쌍이 맞는다면 
    					#스택에 남아있는게 없어야 하니까
        return 'YES'	# YES를 반환합니다
    else:
        return 'NO' 	# 아니면 'NO'

import sys						# 스택 문제를 풀고 처음으로 시간초과가 떠서 알아왔습니다.. 
T = int(sys.stdin.readline())
for _ in range(T):
    bracket = sys.stdin.readline()
    stack = []  ########사실 저 위에 함수가 아니라 이부분이 틀렸는데요....
    #스택을 할때마다 초기화해줘야해요.... 틀린 값이 들어있다면 다음 사례도 틀리거등요..... 기초적인 부분이니까 꼭 기억하기!!!!

    result = gal(bracket)
    print(result)

오랜만에 백준 풀이로 돌아왔습니다 ~~~~

풀다가 제 이름 나와서 반가웠걸랑여 ^ ___________- ^

1 3 -1 4 1 7

2 -1

2 5 8 3 -4 -11

-1 2

내풀 🦷

# 19532. 수학은 비대면 강의입니다
# 연립방정식의 x, y 값을 구하라
a, b, c, d, e, f = map(int, input().split())
x = -999
y = -999
answer = []
for x in range(-999, 1000):
    for y in range(-999, 1000):
        if a * x + b * y == c and d * x + e * y == f:
            answer.append(x)
            answer.append(y)

result = ' '.join(map(str, answer))
print(result)

너무 무식하게 브루트 포스를 잘 적용해야 했다고 해야하나요 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 환장..

-999부터 999까지 중에 있다고 해서 한번 넣어봤어라 ㅋㅋㅋㅋㅋㅋ

x, y에 해당하는 값을 answer 리스트에 넣어줬고요

리스트의 대괄호 없이 나와야 하니까 조인함수를 통해 풀어줬습니다...

다른 분들 풀이를 보니까 

x와 y를 a, b, c, d, e, f를 사용해서 한쪽으로 분배를 한 후에 

for 문 없이 바로 푸셨더라구요 !!

한 수 배웠습니다👍👍

2차원 배열에서 오늘 수업 복습용으로 스터디원이 추천해줘서 풀어봤는데..

재밌는(?) 문제였습니다 🤣🤣🤣🤣🤣🤣🤣

오늘 배웠던 브루트 포스에 관해 잠시 소개해 드리며는...

고지식한 알고리즘(Brute Force)

  : 문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식으로 동작

 +) 고지식한 패턴 검색 알고리즘의 시간 복잡도

  : 최악의 경우 시간 복잡도는 텍스트의 모든 위치에서 패턴을 비교해야 하므로 O(MN)이 됨

  M : 찾을 패턴의 길이 / N : 전체 텍스트의 길이

# 브루토 포스 함수로 구현하기
def BruteForce(p, t):
    M = len(p)
    N = len(t)
    for i in range(N-M+1):
        for j in range(M): # 패턴의 길이만큼 순회
            # 패턴 매칭
            if t[i + j] != p[j]:
                break  # 매칭 실패
            else:
                # 검색 성공
                return i  # t인덱스 반환

    # 검색 실패
    return -1

p = 'is'
t = 'This is a book~!'

result = BruteForce(p, t) 
print(result) # 2

다음에 또 재밌는 문제 가지고 돌아올께영