[백준]11967 불 켜기 - 골드 2
[오늘의 문제]
https://www.acmicpc.net/problem/11967
[오늘의 학습 키워드]
- 그래프 이론
- 그래프 탐색
- 너비 우선 탐색, BFS
- 구현
1. 문제설명
암소 배시는 불이 켜진곳 으로만 이동이 가능합니다.
1, 1 위치에 다른 방의 불을 켜고 끌 수 있는 스위치가 있을 때 해당 방의 불을 켠 후 불이 켜진방으로 이동이 가능합니다.
이렇게 해서 배시가 이동이 가능한 방의 개수를 구하는 문제 입니다.
[제한사항]
- 시간 제한 2초
- 메모리 제한 512MB
- 2 ≤ N ≤ 100
- 1 ≤ M ≤ 20,000
2. 접근방식
배시가 이동 가능한 좌표의 크기는 N x N 이고 불이 켜진 정보가 M개의 줄에 걸쳐 주어집니다.
이때 불의 정보는 x1, y1 -> x2, y2의 불을 켤 수 있습니다.
이 구조는 딕셔너리의 구조와 비슷하죠
딕셔너리의 키, 밸류 구조처럼 키값이 되는 1, 1 위치에서 켤 수 있는 스위치의 정보는 1, 2 / 1, 3 등이 주어지죠
따라서 입력을 받을때 딕셔너리 구조를 이용하여 입력을 받아 현재 위치에서 불을 켤 수 있는 위치를 모두 저장해 줍니다.
모든 저장이 완료되면 1, 1 위치부터 BFS 탐색을 실시하는데
BFS 탐색시 몇 가지 순서가 존재합니다.
1. 현재 위치에서 불을 켤 수 있는 곳을 찾아보기
2. 다음 위치의 불이 안켜져 있다면 불을 켜주기
3. 불을 켜주었으니 불이 켜진 방의 수를 늘려주기
4. 불이 켜진 방으로 이동
5. 이동한 방에서 인접한 4방향 중 불을 켤 수 있고 이동이 가능한지 찾아보기
6. 이동이 가능하면 이동 후 불을 켜주기
이런 방식으로 순서를 세어주면 될 것입니다.
그렇다면 현재 위치에서 불을 켤 수 있는 곳을 찾기 위해서는 딕셔너리의 키, 밸류 구조에 접근해야 하죠
저장할때 defaultdict를 리스트로 초기화하여 값을 키에 맞게 값을 저장해주고 접근하면 됩니다.
그렇다면 반복문을 이용해 현재 위치에서 불을 켤 수 있는 모든 위치를 찾아서 불을 켜줍니다.
이때 다음 위치의 불이 안켜져 있어야 불이 켜진 방의 수가 늘어나게 됩니다.
또한 불이 켜진 방으로 이동해야 하니 불을 키고 끄는 것을 관리하기 위한 리스트 1개가 필요하고
해당 방으로 이동 정보를 저장할 리스트가 1개 필요합니다.
이까지 구조를 잡았으니 코드로 자세히 설명해 보겠습니다.
3. 코드
import sys
input = sys.stdin.readline
from collections import deque, defaultdict
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def BFS():
# 불 켜진 방의 갯수
answer = 1
visited = [[0] * N for _ in range(N)] # 방문 배열
lights = [[0] * N for _ in range(N)] # 불 켜진곳 찾기
visited[0][0] = 1 # 초기값 설정
lights[0][0] = 1 # 초기값 설정
queue = deque([(0, 0)])
while queue:
x, y = queue.popleft()
# 1. 현재 위치에서 불 켤수 있는 곳 찾기
for x2, y2 in info[(x, y)]:
# 2. 다음 위치의 불이 안켜진 경우 불을 켜주기
if not lights[x2][y2]:
lights[x2][y2] = 1
answer += 1 # 3. 방 갯수 +1
# 이때 이 위치를 방문한 적이 있다면 해당 위치로 이동 하여 불을 더 켤 수 있는 곳 찾아주기
if visited[x2][y2] == 1:
queue.append((x2, y2))
# 현재 위치를 기준으로 불 켤 수 있는 모든 곳을 찾았다면 이제 해당 위치로 이동해 주기
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
# 이동의 조건은 격자판을 벗어나지 않고 다음 위치가 방문한 적이 없어야 한다.
if 0 <= nx < N and 0 <= ny < N:
# 여기서 두 조건을 and로 묶지 않은 이유는 위에서 불을 켜기전에 이미 방문한 흔적을 찾는 경우가 있기 때문
# 먼저 방문하고 나중에 불을 켤 수 있다면 이 경우에도 정답이 늘어나야 하기 때문
if not visited[nx][ny]:
visited[nx][ny] = 1 # 따라서 방문 처리와 불을 켜고 이동하는 처리를 따로 해주는 것
if lights[nx][ny]:
queue.append((nx, ny))
return answer
# 입력
N, M = map(int, input().split())
info = defaultdict(list)
for _ in range(M):
x1, y1, x2, y2 = map(int, input().split())
info[(x1 - 1, y1 - 1)].append((x2 - 1, y2 - 1))
print(BFS())[코드설명]
import sys
input = sys.stdin.readline
from collections import deque, defaultdict
# 입력
N, M = map(int, input().split())
info = defaultdict(list)
for _ in range(M):
x1, y1, x2, y2 = map(int, input().split())
info[(x1 - 1, y1 - 1)].append((x2 - 1, y2 - 1))
print(BFS())
앞서 입력을 받을때 defaultdict를 이용하여 키와 밸류의 형태로 값을 저장해 주기 위해 M개의 이동 정보를 defaultdict에 저장
이동 정보를 저장할 때는 격자판의 이동 정보에 맞추기 위해 기존의 값에서 1씩 빼주기
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def BFS():
# 불 켜진 방의 갯수
answer = 1
visited = [[0] * N for _ in range(N)] # 방문 배열
lights = [[0] * N for _ in range(N)] # 불 켜진곳 찾기
visited[0][0] = 1 # 초기값 설정
lights[0][0] = 1 # 초기값 설정
queue = deque([(0, 0)])
BFS 탐색을 실시하는데 이미 1, 1 위치는 불이 켜져 있기 때문에 answer는 1부터 시작
방문처리를 위한 배열과, 불을 켜고 끄기 위한 배열 2개를 생성하고
1, 1 위치에 대해 초기화 해주고, queue에 최초 좌표 입력
while queue:
x, y = queue.popleft()
# 1. 현재 위치에서 불 켤수 있는 곳 찾기
for x2, y2 in info[(x, y)]:
# 2. 다음 위치의 불이 안켜진 경우 불을 켜주기
if not lights[x2][y2]:
lights[x2][y2] = 1
answer += 1 # 3. 방 갯수 +1
# 이때 이 위치를 방문한 적이 있다면 해당 위치로 이동 하여 불을 더 켤 수 있는 곳 찾아주기
if visited[x2][y2] == 1:
queue.append((x2, y2))
# 현재 위치를 기준으로 불 켤 수 있는 모든 곳을 찾았다면 이제 해당 위치로 이동해 주기
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
# 이동의 조건은 격자판을 벗어나지 않고 다음 위치가 방문한 적이 없어야 한다.
if 0 <= nx < N and 0 <= ny < N:
# 여기서 두 조건을 and로 묶지 않은 이유는 위에서 불을 켜기전에 이미 방문한 흔적을 찾는 경우가 있기 때문
# 먼저 방문하고 나중에 불을 켤 수 있다면 이 경우에도 정답이 늘어나야 하기 때문
if not visited[nx][ny]:
visited[nx][ny] = 1 # 따라서 방문 처리와 불을 켜고 이동하는 처리를 따로 해주는 것
if lights[nx][ny]:
queue.append((nx, ny))
return answer
입력된 좌표를 기준으로 2가지 동작을 나누어 수행합니다.
1. 현재 위치를 기준으로 불을 켤 수 있는 곳을 찾고 모둔 켠 후 다음 이동 위치로 저장
2. 더이상 현재 위치에서 불을 켤수 있는 곳이 없는 경우 불이 켜진 다음 위치로 이동
1번의 경우 현재 좌표정보 x2, y2 에는 1, 1 위치에서 불을 켤수 있는 좌표 정보가 저장 되죠
예시로 따지면 1, 2 와 1, 3이 될 것입니다.
이 값들이 존재하기 때문에 현재 위치에서 불을 켤 수 있는 다음 위치를 우선적으로 모두 켜줍니다.
이때 이 좌표값들이 불이 켜져있지 않다면 불을 키면서 불이 켜진 방의 갯수를 늘려주죠
이게 가능한 이유는 해당 방의 불을 1, 1 위치에서 켤 수 있기 때문입니다.
정답이 배시가 불을 켤 수 있는 방의 최대 갯수를 구하는 것이기 때문이죠, 따라서 불을 켜주고 정답을 늘려줍니다.
이때 이 위치를 방문한 적이 있는 경우 배시는 이 위치로 이동이 가능하죠 왜냐하면 불이 켜졌기 때문입니다.
이동 정보는 queue에 저장되기 때문에 방문한 적이 있다면 배시가 이동후 다시 4방향 탐색을 통해 불을 켤 수 잇는 위치를
더 찾아줄 수 있습니다. 따라서 해당 위치를 queue에 저장해 줍니다.
1번의 동작이 모두 종료 되었다면 현재 1,1 위치를 기준으로 4방향 탐색을 통해 배시가 이동 가능한 위치를 찾아 주어야 합니다.
이동이 가능한 곳은 격자판을 벗어나지 않고 아직 방문하지 않은 불이 켜진 방이어야 하죠
이때 불이 켜져 있지 않은 곳도 방문한 적이 없다면 방문 처리는 실시하고 queue에 이동 정보는 저장하지 않는데 이 이유는
앞서 1번에서 우선 방문하고 뒤늦게 불이 켜지는 경우가 있기 때문입니다. 이때 뒤늦게 불이 켜진다면 배시가 해당 위치로
이동이 가능하기 때문에 이동 정보를 저장해주게 되죠
그게 아닌 방문한적이 없고 불이 켜진 방은 queue에 모두 넣어주게 됩니다.
모든 동작이 완료되면 배시가 이동하며 불을 켠 갯수는 answer에 저장됩니다. 이 answer return 으로 출력해주면 되겠죠
4. 결과
[회고]
이번 문제의 경우 처음 문제의 설명을 보고는 잘 이해가 가지 않았습니다.
입력으로 주어지는 값이 틀리게 보였기 때문입니다.
값이 틀리게 주어지는데 힌트에서는 각 좌표로 이동하며 불을 켜서 배시가 불을 켤수 있는 방의 갯수가 5개로 출력되어 잘 이해가 가지 않았습니다.
그러나 문제를 다시보고 M개의 줄에 걸쳐 불을 켤수 있는 방의 정보가 주어져서
위와 같은 조건들을 세울 수 있었죠
여기서 queue에 이동 정보를 저장해주는 과정이 굉장히 중요했습니다.
쓸데 없는 이동정보가 저장된다면 무조건 시간 초과가 났기 때문입니다.
최소의 이동 정보만 저장하기 위해서는 이동 가능 조건을 찾아 주고 그에 맞게끔 설정해 주었어야 합니다.
그러나 이동 정보가 중복 저장될 수 있었습니다.
이 과정을 최소화 하는게 중요했죠
이동 가능한 위치는 불이 켜져있는 아직 방문하지 않은 위치 였습니다.
그러나 불만 켜고 이동을 못하는 경우도 있고
방문하고 불을 켜지 않는 경우도 있었죠
모든 조건에 맞춰 조금씩 수정해가며 문제를 해결할 수 있었습니다.