인프런 커뮤니티 질문&답변

이 문제를 풀다가 의문이 들었는데요 visitied를 사용할 필요가 있었는지 의문이 듭니다.

public static int catch_me(int cony_loc, int brown_loc){
    int time = 0;
    Queue<int[]> q = new LinkedList<>();  //map<위치, 시간>
    q.add(new int[]{brown_loc,0});

    Map<Integer, Boolean>[] visitied = new HashMap[200010];
    for (int i = 0; i < visitied.length; i++) {
        visitied[i] = new HashMap<>();
    }

    while(cony_loc <= 200000){
        cony_loc += time;

        if(visitied[cony_loc].containsKey(time)){
            return time;
        }

        for(int i=0, initialSize = q.size(); i< initialSize; i++){
            int[] info = q.poll();
            int currentPosition = info[0];
            int currentTime = info[1];

            int newTime = currentTime + 1;
            int newPosition ;

            newPosition = currentPosition - 1;
            if(0<= newPosition && newPosition <= 200000) {
                visitied[newPosition].put(newTime, true);
                q.offer(new int[]{newPosition, newTime});
            }
            newPosition = currentPosition + 1;
            if(0<= newPosition && newPosition <= 200000) {
                visitied[newPosition].put(newTime, true);
                q.offer(new int[]{newPosition, newTime});
            }
            newPosition = currentPosition * 2;
            if(0<= newPosition && newPosition <= 200000) {
                visitied[newPosition].put(newTime, true);
                q.offer(new int[]{newPosition, newTime});
            }
        }
        time++;
    }
    return -1;
}

딩코딩코님의 파이썬 풀이를 자바로 변환해봤을 때 이런식으로 코드가 작성이 되었는데 보통 dfs나 bfs에서 visitied는 재방문을 방지하려고 사용하는 것 같은데 이 코드상에는 재방문을 막으려는 부분이 없어보여서요

bfs 내에서 다음 초에 해당하는 위치를 q에 모두 넣게되는데 그럼 비교를 할 때 코니의 다음 시간과 브라운의 다음 시간은 반복문을 돌면서 어차피 조건문에서 체크를 하게되는데 visitied에 저장할 필요가 있나라는 생각이 들더라구요. 그래서

public static int catchMe(int cony, int brown) {
    int time = 0;

    //브라운의 next 위치를 저장할 queue 사용
    Queue<int[]> q = new LinkedList<>();
    q.offer(new int[]{brown, time});

    while(cony <= 200_000){
        cony += time;

        //bfs
        //q.size가 반복문내에서 동적으로 변경이 되므로 고정값을 구해놔야함.
        for(int i = 0, size = q.size() ; i < size; i++){
            //q에 넣은 값을 poll
            int[] posTime = q.poll();
            int currPos = posTime[0];
            int currTime = posTime[1];
         //같은 시간의 코니와 브라운의 위치를 비교하니까 visited를 사용할 필요없어보이데..?
            if(cony == currPos){
                return time;
            }

            //다음 초에 브라운의 위치
            int nextPos[] = {currPos - 1, currPos + 1, currPos * 2};
            for(int pos : nextPos){
                q.offer(new int[]{pos, currTime + 1});
            }
        }
        time++;
    }

    return -1;
}

해당 코드로 다시 작성을 해보았는데 잘되는거는 같은데 혹시 제가 잘못생각하거나 놓치고 있는 부분이 있는지 확인받고싶습니다.