시험

상반기가 오기 전에 방심하다가 제대로 두들겨 맞았다...

개념을 공부 안하기는 커녕 문제도 제대로 보지 않고 서술형을 적지않나....

늦잠을 자서 피곤해서 시험시간에 40분 자지 않나....

문해력이 딸리나 문제를 이해를 못하지 않았나

정신을 크게 차렸던 계기를 가진 것 같다..

 

오전의 본 

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

3197번: 백조의 호수

 

이 문제는 당연히 보자마자 만나는 백조의 위치를 최신화해서 다가가야 한다는 것을 느꼈다.

하지만 큐를 복제하지 않고 일일이 bfs를 돌리거나 필요없이 큐를 여러개 만들어 활용하거나 깊이 생각하지 않고 테케만 

맞추면 되겠지라는 안일함이 컸던 거 같았다.

끝나고 계속 풀어도 시간초과가 났고 지금 생각해보니 한 백조가 움직여서 다른 백조를 만날 때까지 visited배열을 최신화 할 필요 없이

이동하는 방식으로 풀었으면 어땠을까 싶었다.

결국 이 방식은 떠올리지 않았고 동기 녀석의 코드를 보고 이해했다.

       PriorityQueue<Point> pq = new PriorityQueue<>();
        pq.add(start);
        visited = new boolean[R][C];
        visited[start.x][start.y] = true;
        while(!pq.isEmpty()) {
            Point p = pq.poll();
            for (int [] d: directions) {
                int dx = p.x + d[0];
                int dy = p.y + d[1];
                if (0<=dx && dx < R && 0<=dy && dy < C && !visited[dx][dy]) {
                    if(arr[dx][dy] == 'L'){
                        System.out.println(p.count);
                        return;
                    }
                    else {
                        pq.add(new Point(dx,dy,Math.max(p.count, board[dx][dy])));
                    }
                    visited[dx][dy] = true;
                }
            }
        }

 

우선순위큐를 활용해서 bfs 사용하는 방식은 생전 처음 봤고 그래프탐색에 자만했던 나를 다시 겸손하게 만들어준 것 같다.

나는 당연히 bfs를 다 돌려 탐색 중 만나는 최댓값 중 최솟값을 모두 탐색하는 방식을 구현했고 이 부분을 해결하지 못해 수업시간 안에 끝내지 못했던 것 같다.

 

두 번째 오후 시험 볼때는 

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

14865번: 곡선 자르기

 

요 녀석 전에 잠을 자고 일어나도 정신이 몽롱했다.

사실 다 핑계고 좌표를 어떻게 처리하여 봉우리를 만드는가에 대한 뚜렷한 생각이 안났었다.

결국 집에와서 생각해보니 단순한 아이디어로 왼쪽 오른쪽 접점을 구할 수 있었고

괄호구하기 시리즈와 같은 스택문제로 해결할 수 있었던 부분이었다.

 

오늘 참 뜻 깊은 하루였던 것 같다...