<div id="readability-page-1" class="page"><div><img src="https://velog.velcdn.com/images/dongha1992/post/b058f83e-0ad5-43f7-b6fb-a473800ab16a/image.png">
<h2 id="풀이">풀이</h2>
<ul>
<li>이차원 배열 순회하면서 &gt; 0 인 x, y를 기점으로 8면을 dfs로 탐색함</li>
<li>visited로 방문하지 않은 곳만 탐색 </li>
</ul>
<h2 id="코드">코드</h2>
<pre><code>
public class Main {
 static int r, c;
 static int[][] board;
 static boolean[][] visited;
 static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
 static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};

 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 
 int r = sc.nextInt();
 int c = sc.nextInt();
 board = new int[r][c];
 visited = new boolean[r][c];
 
 for (int i = 0; i &lt; r; i++) {
 for (int j = 0; j &lt; c; j++) {
 board[i][j] = sc.nextInt();
 }
 }
 
 int answer = 0;
 for (int i = 0; i &lt; r; i++) {
 for (int j = 0; j &lt; c; j++) {
 if (board[i][j] &gt; 0 &amp;&amp; !visited[i][j]) {
 dfs(i, j);
 answer++;
 }
 }
 }
 System.out.println(answer);
 }
 
 public static void dfs(int x, int y) {
 visited[x][y] = true;
 
 for (int k = 0; k &lt; 8; k++) {
 int nx = x + dx[k];
 int ny = y + dy[k];
 
 if (nx &gt;= 0 &amp;&amp; nx &lt; r &amp;&amp; ny &gt;= 0 &amp;&amp; ny &lt; c &amp;&amp; board[nx][ny] &gt; 0 &amp;&amp; !visited[nx][ny]) {
 dfs(nx, ny);
 }
 }
 }
}</code></pre>
<h2 id="정리">정리</h2>
<ul>
<li>백준에서 메모리 초과 나오는데 왜 그러지는 모르겠다</li>
<li>백준이랑은 안 맞는 듯</li>
</ul></div></div>

삶도 재입학이 되나요?

풀이
이차원 배열 순회하면서 > 0 인 x, y를 기점으로 8면을 dfs로 탐색함
visited로 방문하지 않은 곳만 탐색 
코드
public class Main {
 static int r, c;
 static int[][] board;
 static boolean[][] visited;
 static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
 static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 int r = sc.nextInt();
 int c = sc.nextInt();
 board = new int[r][c];
 visited = new boolean[r][c];
 for (int i = 0; i < r; i++) {
 for (int j = 0; j < c; j++) {
 board[i][j] = sc.nextInt();
 }
 }
 int answer = 0;
 for (int i = 0; i < r; i++) {
 for (int j = 0; j < c; j++) {
 if (board[i][j] > 0 && !visited[i][j]) {
 dfs(i, j);
 answer++;
 }
 }
 }
 System.out.println(answer);
 }
 public static void dfs(int x, int y) {
 visited[x][y] = true;
 for (int k = 0; k < 8; k++) {
 int nx = x + dx[k];
 int ny = y + dy[k];
 if (nx >= 0 && nx < r && ny >= 0 && ny < c && board[nx][ny] > 0 && !visited[nx][ny]) {
 dfs(nx, ny);
 }
 }
 }
}
정리
백준에서 메모리 초과 나오는데 왜 그러지는 모르겠다
백준이랑은 안 맞는 듯

99클럽 코테 스터디 31일차 - bfs

댓글