[백준] 16953번 - A → B 풀이 시간: 40분이내 1) 문제 해결 아이디어 리플릿에서 코드를 짜고 실행을 했을 때는 graph크기를 (10**9 _+ 1) 로 생성하니 그냥 종료 되었다. 크기를 수정하니 전혀 문제가 없었으나 제출할 때 메모리 초과 오류가 생겼다. 코드를 짜는 것은 쉬웠는데 오류를 고치는데 시간이 많이 걸렸다. 모든 BFS 문제는 graph를 만들어서 문제를 푼다는 고정관념때문에 틀린 문제였다. 항상 graph를 만들어 문제를 풀다보니 자연스레 또 그래프를 만들 생각만 했던 것 같다. BFS를 풀기 위해서는 큐만 있으면 된다!! 1. 큐 생성 및 (시작값, 누적 연산횟수) 형태로 삽입 2. 2가지 연산 수행 2-1. 큐에서 하나 꺼내기 2-2. 2가지 연산한 결과값(nx)이 1보..
[백준] 2206번 - 벽 부수고 이동하기 풀이 시간: 1) 문제 해결 아이디어 언제 벽을 부숴야 할지 조건을 떠올리는게 쉽지 않았다. 최근에 푼 BFS 문제 중에는 난이도가 가장 높은 문제인 것 같다. 여러가지 아이디어를 떠올려보고 시도해봤으나 잘 되지 않고 시간이 너무 지체되서 풀이를 봤는데도 한 번에 이해가가지 않아 복습이 필요한 문제다. Q. visited 3차원 배열 생성 시 초기화하는 이유는? visited를 생성하는 부분에서 시작 좌표(0, 0)에 해당하는 부분을 1로 초기화해야한다. 그렇지 않으면 (0,1)이나 (1,0)의 인접좌표를 검사할 때 (0, 0)의 graph값이 0이므로 검사를 진행하게 되는 문제가 발생한다. 사실상 정답에 영향을 미치지는 않지만 헷갈리니 그냥 다 초기화하는 걸로..
[이코테] 문제2 - 미로 탈출(152p) 풀이 시간: 40~45분 이내 1) 문제 해결 아이디어 BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색한다. 상하좌우로 연결된 모드 노드의 길이가 1로 동일하므로 (1, 1) 지점부터 BFS를 수행하여 모든 노드의 최단 거리 값을 기록하면 해결 가능함 1. 종료 조건 설정 항상 출구값을 리턴하기 때문에 종료 조건이 없어도 결과는 똑같다. 다만 종료 조건을 넣어주면 해당 좌표가 출구지점이 될 떄 까지만 탐색을 진행한다. 2. 탐색 조건에서 시작점 제외 상하좌우 탐색 시, 시작점은 갔던 곳이므로 탐색하지 않도록 조건을 설정하였다. 책의 코드처럼 시작점일 때도 탐색하게 해도 결과값은 달라지지 않지만 값이 3으로 덮어쓰여지게 된다. 1. 시작..
