https://www.acmicpc.net/problem/4963흔한 구역 개수 구하는 문제. 근데 특이한 건 대각선도 연결되어 있는 걸로 생각해야 하는 게 특이하다. 그것만 생각하면 나머진 쉬운 문제.아이디어- 일반적인 상하좌우탐색에서 추가로 대각선 방향도 추가해준다.전체 코드import syssys.setrecursionlimit(10**6)dx = [0, 0, 1, -1, 1, -1, 1, -1]dy = [1, -1, 0, 0, 1, -1, -1, 1]def dfs(x, y): if x = H or y = W: return False #print(x, y) if island[x][y] == 1: island[x][y] = 0 dfs(x, y + ..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 시간제한 3초로 매우 길지만 너무 복잡하지 않은 문제. 아마 테스트 케이스가 여러 개라서 시간제한을 널널하게 둔 거 같다. 아이디어 1. 그래프 일단 보자마자 그래프를 써야 한다고 생각했다. 문제 조건에서 팀이 되려면 서로가 꼬리를 물듯 사이클이 생겨야 한다. 그럼 이 문제는 그래프에서 '사이클을 어떻게 찾고 판별하냐'에 대해서 생각하면 된다. 2. dfs 방문 유무를 통해 사이클이 생겼는지 안 생겼는..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 아이디어 1. 두 가지로 나눠 생각하면 테트로미노 도형 만들기 종이 위에 올리기 2. 도형 만들기 도형이 회전이나 대칭도 가능하니 dfs를 사용하면 T도형 빼고 전부 다 만들 수 있다. dfs 탐색 깊이를 4까지 설정하면 도형을 확인할 수 있다. T 모양은 따로 함수를 만들어 처리했다. 3. 종이에 도형 놓기 시간제한이나 N, M 크기를 보고 브루트 포스를 사용하기로 결정했다. 각 위치마다 만들어..

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 파이썬이라 억까당함. 난이도는 낮지만 시간 초과로 고생했다. 맨 처음 bfs로 풀었을때 시간 초과가 채점 70%에서 자꾸 걸리길래 방법이 틀린 줄 알았다. 아마 파이썬이 아니였으면 맞았을 거 같다. from collections import deque import sys count = 0 N = int(input()) home = [] for _ in range(N): h..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 구역의 수를 찾는 문제 근데 이제 색약을 곁들인 dfs나 bfs 중 하나를 택해 문제를 해결하면 된다. 해결하는 방법이 정말 다양하지만 그중 하나만 작성함. 문제 풀이 이 문제는 색약일때와 색약이 아닐 때 각각 어떻게 처리하냐에 풀이가 다를 것이다. 나는 배열을 복사해서 색약일 때(R == G) 따로 함수를 만들어 탐색하도록 만들었다. 다른 방법으로는 색약이 아닌 경우 탐색을 해주고 원래 ..