📃

22년 12월 3주차 회고록(회고사진)

•

회의 날짜: 2022/12/20

•

회의 장소: discord 라운지

•

참석자: 김솔배, 구연지, 안지영

[회고 사진]

[문제]

1697번: 숨바꼭질

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

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

[이번 스터디 공부한 내용]

김솔배

•

BFS를 사용해서 풀 수 있을거 같아 사용해 문제를 해결했다

BFS코드 (방문 체크하는것을 빼먹었다.)

해결코드 - BFS로 해결

public class Main {
    //이동할 수 있는 경우
    int[] dx = {1, -1, 2};

    private int solution(int n, int k) {
        boolean[][] dp = new boolean[1][100001];
        Queue<int[]> q = new LinkedList<>();
        int answer = 0;
        q.add(new int[]{n, answer});
        dp[0][n] = true;

        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int x = curr[0];
            int cnt = curr[1];

            if(x == k) {
                answer = cnt;
                break;
            }

            for (int i = 0; i < dx.length; i++) {
                int nX;
                if(i != 2) nX = x + dx[i];
                else nX = x * dx[i];

                if (nX < 0 || nX > 100000) continue;

                if(dp[0][nX] == false){
                    dp[0][nX] = true;
                    q.add(new int[]{nX, cnt + 1});
                }
            }
        }
        return answer;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        Main s = new Main();
        System.out.println(s.solution(n, k));
    }
}
Java
복사

구연지

(1) 재귀 함수 이용하기

import sys

def calculate_move_count(start, end):

    if start == end:
        return 0
    elif start > end:
        return calculate_move_count(end, start)

    if (start - end == 1):
        return 1

    if end % 2 == 0:
        return 1 + calculate_move_count(start, end//2)

    # 2배 이동하는 것을 생각하기 -> 홀수인 경우 1과 짝수로 나누기
    if (end % 2 == 1):
        return 1 + calculate_move_count(start, end - 1)




input = sys.stdin.readline().replace("\n", "").split(" ")
start = int(input[0])
end = int(input[1])

print(calculate_move_count(start, end))
Python
복사

메모리 초과 에러 발생

(2) BFS 이용하기

Python
복사

안지영

대표적인 BFS 문제이다.

현재 위치에서 +1, -1, *2인 위치로만 이동이 가능하다. 범위를 벗어나거나 이미 방문한 노드이면 무시하고 그렇지 않은 경우 큐에 넣어서 앞으로 방문하도록 하였다. 이동한 위치가 목표 지점이면 while문을 탈출하도록 처리하였다. 또한 depth도 위치와 함께 튜플형식으로 큐에 넣어서 깊이(몇 초 걸리는지)를 기록하도록 하였다.

# 1697 숨바꼭질 https://www.acmicpc.net/problem/1697

from collections import deque

def solution(start, end):
    queue = deque([(start, 0)])
    
    visited = [False] * 1000001
    
    while queue:
        x, depth = queue.popleft()
        
        if x == end:
            return depth
        
        visited[x] = True
        
        for tmp_x in (x+1, x-1, 2*x):
            
            if tmp_x < 0 or tmp_x > 100000 or visited[tmp_x] == True:
                continue
            
            queue.append((tmp_x, depth + 1))

start, end = map(int, input().split())
print(solution(start, end))
Python
복사

[어려웠던 부분]

•

 김솔배

처음 문제를 보자마자 BFS문제라고 생각이 들었다.
문제를 풀면서 자꾸 메모리 초과에러가 났다
덕분에 BFS에 대해 더 알아갈 수 있었다.
Plain Text
복사

•

 구연지

BFS 문제를 알고리즘으로 구현하는 데에 시간이 걸리는 것 같다
BFS와 DFS 알고리즘을 다시 정리하고 구현하는 연습을 해봐야겠다.
Plain Text
복사

•

 안지영

깊이(몇 초 걸리는 지)를 어떻게 기록해야할지 고민하는데 시간이 좀 걸렸던 것 같다.
Plain Text
복사

[금주의 꿀팁 & 인사이트!]

•

 김솔배

BFS는 항상 반문체크를 해주어야한다
그렇지 않으면 넓이만큼 계속 호출하기 때문에 메모리와 공간이 부족해 진다.
Plain Text
복사

•

 구연지

꿀팁은 딱히 없는 것 같다.
Plain Text
복사

•

 안지영

깊이를 기록해야하는 경우 큐에 그 노드와 함께 저장하면 각 노드의 깊이를 나중에도 파악하기 편한 것 같다.
Plain Text
복사

[금주의 느낀 점]

•

 김솔배

알고리즘의 개념을 정확히 알고있어야 인터넷이나 다른 정보를 참고하지 않고 풀 수 있을거 같다.
코딩 테스트를 대비해서 꼭 핵심개념들을 떠올려 문제를 푸는 연습을 하자
Plain Text
복사

•

 구연지

왜 문제를 접근할 때 재귀함수를 이용하는 것이 편할까?라는 생각을 해보았는데,
아마 문제별로 어떤 알고리즘을 이용해서 접근하면 좋을지에 대한 것이 정리되지 않은 것 같아서
그런 것 같다.
앞으로는 (1) 매일 한 문제씩 풀면서 (2) 어떻게 접근하면 좋을 것 같다는 것을 메모하고
비교하는 습관을 길러야겠다.
Plain Text
복사

•

 안지영

BFS 처음엔 너무 막막했는데 계속 여러 문제들을 풀다 보니 익숙해진 것 같다. 
오히려 DFS보다 훨씬 나은 것 같다🙈 그래도 더 어려운 문제로 연습해보자 꼭
Plain Text
복사