문제 https://www.acmicpc.net/problem/13265 13265번: 색칠하기 각 테스트 케이스에 대해서 possible 이나 impossible 을 출력한다. 2 가지 색상으로 색칠이 가능하면 possible. 불가능하면 impossible 이다. www.acmicpc.net 접근 예제를 그래프로 그려서 확인해 보자. 각 노드를 R, G로 색칠해야 한다고 하자. 1번을 R로 색칠하면 문제의 조건에 의해 2, 3이 G로 색칠되어야 한다. 그런데 2번과 3번도 연결되어 있으므로 서로 다른 색이 되어야 하는데 G로 동일하므로 해당 그림은 두 가지 색으로 색칠할 수 없다. 이를 확인하는 방법은 BFS를 사용하여 구현할 수 있다. 시작 노드를 하나의 색으로 정해 칠한 뒤, 자신과 인접한 노드들..

문제 https://www.acmicpc.net/problem/14629 14629번: 숫자 조각 곧 7살을 맞이하는 준하는 유치원에서 숫자가 적힌 나무 조각들을 가지고 노는 것을 좋아한다. 숫자 조각은 총 10개이며, 각각의 조각엔 0부터 9까지의 숫자가 한 숫자씩 적혀있다. 준하는 각 숫 www.acmicpc.net 접근 기본적인 백트레킹(DFS) 문제 N이 1,000,000,000,000 까지로 매우 크다. 그런데 생각해보면 0부터 9까지 만들 수 있는 것은 9자리로 한정되고 그마져도 9876543210 을 초과하는 순간 답은 9876543210으로 고정된다. 그 이외에는 0부터 9까지를 사용하도록 DFS를 만들면서 만들어진 수가 $N$과 얼마나 차이가 나는지를 확인하고 갱신해주면 해결된다. 정답 ..

해당 문제는 제로베이스 벡엔드 스쿨 11기 자료구조 문제입니다. 문제 설명 이메일 정보가 들어있는 2차원 문자열 배열인 accounts가 입력으로 들어온다. accounts[i][0]은 사람의 이름, accounts[i][1]은 이메일을 나타내는 구조로 되어있다. 한 사람이 여러 개의 이메일을 소유하기도 하며, 동명이인이 존재할 수 있다. 이때 구분하는 방법은 다음과 같다. 이름이 동일하고, 이메일이 다르다면 동명이인이다. 이름이 동일하고, 이메일 중 동일한 이메일이 존재한다면 동일인이다.(복수의 이메일을 가진 사람) 이때 이메일 정보를 취합하여 출력하는 프로그램을 작성하라 문제 접근 처음 보면 난해해 보인다. 하지만 입력 부분을 잘 보면 그래프로 모델링할 수 있다. 위의 조건 중 하나로 이름이 같고, ..

해당 문제는 제로베이스 벡엔드 스쿨에서 만든 문제입니다. 문제의 설명 N x M 크기의 행렬인 board와 문자열 word가 입력으로 들어올 때 행렬 board에서 word를 찾을 수 있는지 확인하는 문제이다. 이때 word로 찾아지는 문자열은 모두 인접해 있어야 한다. 예를 들어 위와 같은 board가 주어졌다고 할 때, word로 ABCCED가 들어왔다면 위 사진의 색칠된 것과 같이 찾을 수 있게 되어 true를 반환하게 된다. 문제의 접근 word로 주어진 문자열을 찾을 때 모든 문자들이 인접해야 한다는 조건이 있다. 이는 board의 각 칸을 하나의 노드로 생각할때 상하좌우로 간선이 연결된 그래프로 모델링이 가능하다. 즉 문제는 이 그래프에서 탐색을 통해 word와 동일한 문자열을 만들어낼 수 있..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/81302 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근방법 input에 들어오는 2차원 배열의 각 행이 하나의 test case로 생각될 수 있고, 각 행들은 적절한 문자열 처리를 하면 2차원 배열로 다시 만들 수 있다. 이 2차원 배열이 문제의 조건인 맨해튼 거리 2 이하로 모든 사람이 배치되어 있는지 확인하는 문제이다. 처음 문제를 해결할 때 DFS로 해결했었다. 각 방을 탐색하며 원래 위치와 현재 위치의 좌표를 이용해 맨해튼 거리를 구..

https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 풀이 방법 검을 습득할 시 모든 벽을 통과할 수 있다. 그 전에는 벽을 통과하지 못하므로, 두 개의 맵을 준비해야 한다. 하나는 검을 습득하지 못한 상태로 이동하는 맵, 다른 하나는 검을 습득한 상태에서의 맵이다. 두 개의 맵이 준비되어야 하므로 맵은 3차원 리스트 형태(배열 형태)가 되어야 할 것이다. 물론 방문 확인 배열 역시 3차원이 되어야 한다. 만약 검이 용사가 이동할 수..