'이것이 코딩 테스트다 with 파이썬(나동빈)' 책을 기반으로 작성한 글입니다.
📝문제1. 백준 18428번(감시 피하기)
- 문제
https://www.acmicpc.net/problem/18428
- 나의 코드💻
from collections import deque
n = int(input())
graph = [[]]
for i in range(n):
graph.append(list(input().split()))
dx = [-1, 0, 1, 0] # 상 우 좌 하
dy = [0, 1, 0, -1] # 상 우 좌 하
q = deque(1)
while q:
v = q.popleft()
for i in graph[v]:
if graph[v][i] == 'T':
for k in range(4):
# 네 방향으로 이동
nx = x + dx[k]
ny = y + dy[k]
if nx < 0 or nx > n or ny < 0 or ny > n:
break
if graph[nx][ny] == 'S':
graph[n- 정답 코드💻
from itertools import combinations
n = int(input()) # 복도의 크기
board = [] # 복도 정보 (n x n)
teachers = [] # 모든 선생님 위치 정보
spaces = [] # 모든 빈 공간 위치 정보
for i in range(n):
board.append(list(input().split()))
for j in range(n):
# 선생님이 존재하는 위치 저장
if board[i][j] == 'T':
teachers.append((i, j))
# 장애물을 설치할 수 있는 (빈 공간) 위치 저장
if board[i][j] == 'X':
spaces.append((i, j))
# 특정 방향으로 감시를 진행(학생 발견 : True, 학생 미발견 : False)
def watch(x, y, direction):
# 왼쪽 방향으로 감시
if direction == 0:
while y >= 0:
if board[x][y] == 'S': # 학생이 있는 경우
return True
if board[x][y] == 'O': # 장애물이 있는 경우
return False
y -= 1
# 오른쪽 방향으로 감시
if direction == 1:
while y < n:
if board[x][y] == 'S': # 학생이 있는 경우
return True
if board[x][y] == 'O': # 장애물이 있는 경우
return False
y += 1
# 위쪽 방향으로 감시
if direction == 2:
while x >= 0:
if board[x][y] == 'S': # 학생이 있는 경우
return True
if board[x][y] == 'O': # 장애물이 있는 경우
return False
x -= 1
# 아래쪽 방향으로 감시
if direction == 3:
while x < n:
if board[x][y] == 'S': # 학생이 있는 경우
return True
if board[x][y] == 'O': # 장애물이 있는 경우
return False
x += 1
return False
# 장애물 설치 이후에, 한 명이라도 학생이 감지되는지 검사
def process():
# 모든 선생님의 위치를 하나씩 확인
for x, y in teachers:
# 4가지 방향으로 학생을 감지할 수 있는지 확인
for i in range(4):
if watch(x, y, i):
return True
return False
find = False # 학생이 한 명도 감지되지 않도록 설치할 수 있는지의 여부
# 빈 공간에서 3개를 뽑는 모든 조합을 확인
for data in combinations(spaces, 3):
# 장애물 설치해보기
for x, y in data:
board[x][y] = 'O'
# 학생이 한 명도 감지되지 않는 경우
if not process():
# 원하는 경우를 발견한 것임
find = True
break
# 설치된 장애물을 다시 없애기
for x, y in data:
board[x][y] = 'X'
if find:
print('YES')
else:
print('NO')- 비교 분석📖
이 문제는 장애물을 정확히 3개 설치하는 모든 경우를 확인하여, 매 경우마다 모든 학생을 감시로부터 피하도록 할 수 있는지의 여부를 출력해야 한다. 그렇다면 장애물을 정확히 3개 설치하는 경우의 수는 얼마나 될지 생각해보자. 복도의 크기는 N x N이며, N은 최대 6이다. 따라서 장애물을 정확히 3개 설치하는 모든 조합의 수는 최대 10,000 이하의 수이므로 모든 조합을 고려해 완전 탐색을 수행해도 시간초과 없이 문제를 해결할 수 있다. 따라서 모든 조합을 찾기 위해 DFS 또는 BFS를 이용해 모든 조합을 반환하는 함수를 작성하거나, 파이썬의 조합 라이브러리를 이용할 수 있다.
또한 정확히 3개의 장애물이 설치된 모든 조합마다, 선생님들의 위치 좌표를 하나씩 확인하고 각각 선생님의 위치에서 상, 하, 좌, 우를 확인하며 학생이 한 명이라도 감지되는지를 확인해야 한다. 이는 별도의 watch() 메서드를 구현하면 편하다.
답안 예시에서는 DFS/BFS를 직접 이용해 구현하지 않고, 파이썬의 조합 라이브러리를 이용하여 DFS/BFS를 대체하였다.
복도 정보뿐만 아니라 선생님의 위치 정보, 빈 공간의 위치 정보까지 저장해 이를 활용해 문제를 풀어야 했었다. 코드는 좀 길지만 하나하나 뜯어보니 생각보다 복잡한 코드는 없고 잘 이해가 갔다. 조합을 활용하니 확실히 덜 복잡하게 구현할 수 있는 것 같다.
📝문제2. 백준 16234번(인구 이동)
- 문제
https://www.acmicpc.net/problem/16234
- 나의 코드💻
n, l, r = map(int, input().split())
area = [] # 땅
for i in range(n):
area.append(list(map(int, input().split())))
border = [0]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]-> 뒤에 엉터리로 쓴 코드는 너무 말도 안됐는데,, 책의 코드를 보고 쓰는 과정에서 없어져버렸다.. 경계선을 어떻게 표현해야 할지 고민했는데 그러다보니 코드가 정말 이상해지고 말도 안되게 짜졌다.. 경계선에 대한 리스트를 만드는게 아니라 연합에 대한 리스트를 만들어야 하는 문제였다. 그리고 dfs를 써야할지 bfs를 써야할지 고민했는데 bfs를 사용하는 문제였다..
- 정답 코드💻
from collections import deque
n, l, r = map(int, input().split())
graph = []
for _ in range(n):
graph.append(list(map(int, input().split())))
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
result = 0
# 특정 위치에서 출발하여 모든 연합을 체크한 뒤에 데이터 갱신
def process(x, y, index):
# (x, y)의 위치와 연결된 나라(연합) 정보를 담는 리스트
united = []
united.append((x, y))
q = deque()
q.append((x, y))
union[x][y] = index # 현재 연합의 번호 할당
summary = graph[x][y] # 현재 연합의 전체 인구 수
count = 1 # 현재 연합의 국가 수
# 큐가 빌 때까지 반복
while q:
x, y = q.popleft()
# 현재 위치에서 4가지 방향을 확인하며
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 바로 옆에 있는 나라를 확인하며
if 0 <= nx < n and 0 <= ny < n and union[nx][ny] == -1:
# 옆에 있는 나라와 인구 차이가 L명 이상 R명 이하라면
if l <= abs(graph[nx][ny] - graph[x][y]) <= r:
q.append((nx, ny))
# 연합에 추가
union[nx][ny] = index
summary += graph[nx][ny]
count += 1
united.append((nx, ny))
# 연합 국가끼리 인구를 분배
for i, j in united:
graph[i][j] = summary // count
return count
total_count = 0
# 더 이상 인구 이동을 할 수 없을 때까지 반복
while True:
union = [[-1] * n for _ in range(n)]
index = 0
for i in range(n):
for j in range(n):
if union[i][j] == -1: # 해당 나라가 아직 처리되지 않았따면
process(i, j, index)
index += 1
# 모든 인구 이동이 끝난 경우
if index == n * n:
break
total_count += 1
# 인구 이동 횟수 출력
print(total_count)- 비교 분석📖
3-2에서 풀었던 음료수 얼려먹기 문제와 비슷하다고 한다. 각 나라의 위치에서 BFS를 수행하여, 연결되어 있는 모든 나라들(연합)을 찾으면 된다.
책을 보고 따라쳤는데 인덴테이션을 내가 잘못 줘서 자꾸 오류가 떴었다. 몇번 더 풀어봐야 완전히 이해할 수 있는 것 같은 문제..
📝문제3.프로그래머스 블록 이동하기
- 문제
- 나의 코드💻
- 정답 코드💻
- 비교 분석📖
미래의 나에게 넘기기......
정말 궁금한 점이 생겼다. 이런 문제는 도대체 누가, 어떻게, 무슨 생각을 가지고 만들어 내는 것일까? 갑자기 너무 너무 너무 궁금해졌다. 정말 알 수 없다.
안녕하세요, 마지막 문장이 너무 심금을 울리네요... 저도 정말 궁금합니다...
항상 꼼꼼히 분석하시는 것 같아요. 항상 많이 배워가고, 자극받아 갑니다! 저도 다음 주부터는 조금 더 열심히 하겠습니다..! 이번주도 수고하셨어요!!