전체 글
-
[BOJ] #17472 다리 만들기 2Algorithm 2020. 11. 11. 13:41
[BOJ] #17472 다리 만들기 2 삼성 역량테스트 문제였다 MST와 BFS 구현 위주의 문제라 그냥 끝까지 풀어보았다. 그리고 엣지케이스가 생각보다 많아서 꽤 오랜 시간이 걸렸다(..) FLOW 각 섬을 Numbering해야한다. BFS로 진행하였다. 섬과 섬 사이의 거리를 구한다. 이 때, 꼭 일직선으로만 진행해야한다.(진행 후 벡터에 저장하여 edge값으로 사용했다.) 각 섬간의 관계를 가중치 그래프로 나타낸 뒤, Kruskal Algorithm을 적용한다. 가중치의 합을 구하다 보면 result가 0일 때에만 cout= n) { continue; } if (vis[nextX][nextY]) continue; if (map[nextX][nextY] == 1) { map[nextX][nextY] ..
-
[BOJ] #11967 불 켜기Algorithm 2020. 11. 11. 13:36
[BOJ] #11967 불 켜기 문제 농부 존은 최근에 N*N개의 방이 있는 거대한 헛간을 새로 지었다. 각 방은 (1, 1)부터 (N,N)까지 번호가 매겨져있다(2≤N≤100). 어둠을 무서워하는 암소 베시는 최대한 많은 방에 불을 밝히고 싶어한다. 베시는 유일하게 불이 켜져있는 방인 (1,1)방에서 출발한다. 어떤 방에는 다른 방의 불을 끄고 켤 수 있는 스위치가 달려있다. 예를 들어, (1, 1)방에 있는 스위치로 (1, 2)방의 불을 끄고 켤 수 있다. 베시는 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다. 베시가 불을 켤 수 있는 방의 최대 개수를 구하시오. 입력 첫 번째 줄에는 N(2≤N≤100)과, M(1≤M≤20,000)이 정수로 주어진다. ..