문제 선정

우선 하나를 고르면 끝까지 풀어볼 계획이기 때문에 조금 신중하게 고르려고 노력하였다. 특히 저 밑에 섬이라는 문제는 날 건들면 쉽지 않을거야를 온 몸으로 소리지르는 듯 해서 그냥 저 놈부터 조질까 하는 생각이 들었는데 마침 오늘 딱히 할만한 일이 없고 오늘 골드 문제 하나를 스트릭에 넣어두어서 어느정도 "안정"인 상태이니 한 번 건드려보아도 나쁘지 않겠다 생각을 하여 이 문제를 선택하게 되었다.
#BOJ1109

섬

언제나 그렇듯이 문제에 대한 접근 과정부터 시작해보려고 한다. 다만 지도를 보는 순간 아 풀기 싫다라는 생각이 들기 시작하긴 하였다. 문제 이해자체는 되었다. 하지만 구현 과정이 쉽지 않겠다라는 생각을 하였다. 우선 섬을 구성하는 방법과 섬간의 이동방법이 다르기 때문에 이 부분이 먼저 거슬린다고 생각하였다. 이를 위해서 우선 섬들을 구별(?)하는 알고리즘부터 구현하기로 결정하였다. 이거는 기존에 해결하였던 아기 상어 문제와 유사하다고 생각하였다. 기본적으로 한 사이클을 돌고 나서 끝나면 전체 안에 x가 있나 없나 찾는 과정을 갖고 x가 발견되면 continue한 후 cnt를 늘리는 과정을 가졌다. 그래서 island라는 배열 안에 섬을 네이밍하여 넣는 것을 완료하였다.

import sys

N, M = map(int, sys.stdin.readline().split())
arr = [sys.stdin.readline().rstrip() for _ in range(N)]
island = [[]]
dx = [1, -1, 0, 0, 1, 1, -1, -1]
dy = [0, 0, 1, -1, 1, -1, 1, -1]
visited = [[False for _ in range(M)] for _ in range(N)]
q = [[0,0]]
if arr[0][0] == 'x':
   island[0].append([0, 0])
cnt = 0
while q:
   x, y = q.pop()
   visited[x][y] = True
   for i in range(8):
       xx = x + dx[i]
       yy = y + dy[i]
       if xx >= 0 and xx < N and yy >= 0 and yy < M:
           if not visited[xx][yy] and arr[xx][yy] == "x":
               visited[xx][yy] = True
               island[cnt].append([xx, yy])
               q.append([xx, yy])
   flag = 0
   #새로운 시작점(x)가 있을 경우를 위하여
   if len(q) == 0:
       for i in range(N):
           for j in range(M):
               if not visited[i][j] and arr[i][j] == "x":
                   cnt += 1
                   island.append([[i, j]])
                   q.append([i, j])
                   flag = 1
                   break
           if flag:
               break
for i in range(cnt + 1):
   print(island[i])

위는 그에 대한 간단한 코드이다. 솔직히 여기까지는 BFS 몇 번 쳐봤으면 꾸역꾸역 올만한데 이후로는 솔직히 감이 좀 안잡힌다. 우선 여기까지만도 최소 티어가 골드4 이상이라는 생각이 들어서 이 살벌한 문제를 내가 왜 골랐는지에 대한 후회가 조금 들었다. 그래도 위에서 처리한 내용들을 토대로 뭔가 DFS를 하면 감싸고 있는 섬들에 대한 정보를 얻을 수 있지 않을까 하는 생각이 들었다. 하지만 DFS라면 사람 이하의 경지이기 때문에 공부를 좀 더 하고 다시 도전해보기로 결정하였다.